题解 CF773D 【Perishable Roads】

发表于 | 更新于 | 阅读次数：
本文字数： 2.9k | 阅读时长 ≈ 3 分钟

题目大意

  • 附近有$n$个城市，城市两两之间都有双向的道路，道路的长度为$w$，某位旅行者的目的地是城市$s$，但是他不认路，所以他每到一个城市都会向那里的居民询问该往那里走才能到城市$s$，到一个城市的代价为所经过的道路的最小值，现在他想知道从任意一个城市出发到$s$的最小的代价和。他要去的城市$s$还没有定下来，所以请你求出对于所有的$s$的代价和。城市里的居民都很聪明，会对他指出使代价和最小的方案。

要部分分以及中文翻译的同学可以点开这里

  • 出题人太菜了不知道什么部分分的算法，所以数据随机，并且给了正确性较高的乱搞部分分。

  • 如果有用乱搞得到高分的选手可以先上来分享一下做法

题目分析

我一开始的错误想法

很显然，这个路标连接起来之后是一棵树，对于每一个城市的贡献就是这个城市到终点城市$s$的路上的最小值。

然后我就有了一个~~非常睿智的~~想法：就是对于任意一个终点城市$s$，把所有的城市都连在最短边的一端，再由最短边直接连到终点城市$s$。

~~然后。。。这个东西显然是假的~~

正确的想法

不过我们可以考虑对它进行一些~~微$(jù)$小$(dà)$的~~修改让它成为正确的。

考虑这个想法的错误之处：在于最短边的一端到终点的距离可能很长，

所以我们考虑对这个进行计算

最短边的一边到终点城市的路径显然是一条链。

可以发现这条链如果是从终点城市开始递减的

那么答案就是这条链的长度

我们考虑把这个东西再转化一下

对于一个中间有边比之后的边要小的话，那么显然它之前的所有边直接连到最短边就好了。

那么这条最短边的贡献应该为两倍的权值

然后对于一个最短边的点到一个点的距离可以简化成本来存在的路或者是这个点连着一条边的两倍    

然后以最短边的点为起点跑最短路就好了

最后记得加上剩下的边数乘最短边

献上我的丑陋码风代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<algorithm>


char gc()
{
    static char buf[1<<20],*p1=buf,*p2=buf;
    if(p1==p2)
    {
        p2=(p1=buf)+fread(buf,1,1<<20,stdin);
        if(p1==p2)return EOF;
    }
    return *p1++;
}

#define getchar gc

template<typename _Tp>
_Tp read(_Tp& x)
{
    x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}


using namespace std;

long long n,s,ans,minn,a[5005][5005],dis[5005];
bool vis[5005];

inline void dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        dis[i]=a[s][i];
        for(int j=1;j<=n;j++)
        {
            if(i!=j)dis[i]=min(dis[i],a[i][j]*2);
        }
    }
    vis[s]=1;
    for(int i=1;i<=n-1;i++)
    {
        long long minn=~(1LL<<63),v;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j];v=j;
            }
        }
        vis[v]=true;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j])
            {
                dis[j]=min(dis[j],dis[v]+a[v][j]);
            }
        }
    }
}

int main()
{
    read(n);
    minn=0x7fffffffffffffff;
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            read(a[i][j]);
            a[j][i]=a[i][j];
            if(a[i][j]<minn)minn=a[i][j],s=i;
        }
    }
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            a[i][j]-=minn;
            a[j][i]=a[i][j];
        }
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",dis[i]+minn*(n-1));
    }
}