原题链接

考察:最短路

思路:

       是模板题.Johnson算法主要用于处理负权边,它可以让Dijkstra算法计算带负权的最短路问题.

       具体的做法是:建立虚点0,再让0与每个点连一条边,求出0到每个点的最短路,将(u,v)之间的权值w = w+dist[u]-dist[v]. 这样w一定为正,因为最短路更新完后,dist[u]+w>dist[v],将dist[v]左移一定为正.至于正确性证明请看这个blog : GO

       这道题是做法就是spfa判断负环,然后用Johnson算法计算边,然后用dijkstra算法计算最短路和即可.

      时间复杂度O(n*mlog₂n)

 1 #include <iostream> 
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<int,int> PII;
 7 const int N = 6010,M = 3010,INF = 1e9;
 8 int n,m,h[M],idx,cnt[M];
 9 LL dist[M],dis[M];
10 bool st[M];
11 struct Road{
12     int to,ne,w;
13 }road[N+M];
14 void add(int a,int b,int w)
15 {
16     road[idx].to = b,road[idx].w = w,road[idx].ne = h[a],h[a] = idx++;
17 }
18 LL dijkstra(int s)
19 {
20     for(int i=1;i<=n;i++) dist[i] = INF,st[i] = 0;
21     dist[s] = 0;
22     priority_queue<PII,vector<PII>,greater<PII> > q;
23     q.push({0,s});
24     while(q.size())
25     {
26         PII it = q.top();
27         q.pop();
28         int u = it.second;
29         if(st[u]) continue;
30         st[u] = 1;
31         for(int i=h[u];~i;i=road[i].ne)
32         {
33             int v = road[i].to;
34             if(dist[v]>dist[u]+road[i].w)
35             {
36                 dist[v] = dist[u]+road[i].w;
37                 q.push({dist[v],v});
38             }
39         }
40     }
41     LL res = 0;
42     for(int i=1;i<=n;i++)
43       if(dist[i]==INF) res += (LL)i*INF;
44       else res+=(dis[i]-dis[s]+dist[i])*i;
45     return res;
46 }
47 bool spfa(int s)
48 {
49     queue<int> q;
50     memset(dist,0x3f,sizeof dist);
51     dist[s] = 0;
52     q.push(s);
53     st[s] = 1;
54     while(q.size())
55     {
56         int u = q.front();
57         q.pop();
58         st[u] = 0;
59         for(int i=h[u];~i;i=road[i].ne)
60         {
61             int v = road[i].to;
62             if(dist[v]>dist[u]+road[i].w)
63             {
64                 dist[v] = dist[u]+road[i].w;
65                 cnt[v] = cnt[u]+1;
66                 if(cnt[v]>n) return false;
67                 if(!st[v]) q.push(v),st[v] = 1;
68             }
69         }
70     }
71     return 1;
72 }
73 int main()
74 {
75     scanf("%d%d",&n,&m);
76     memset(h,-1,sizeof h);
77     while(m--)
78     {
79         int a,b,c; scanf("%d%d%d",&a,&b,&c);
80         add(a,b,c);
81     }
82     for(int i=1;i<=n;i++) add(0,i,0);
83     if(!spfa(0)) {puts("-1"); return 0;}
84     for(int i=1;i<=n;i++)
85       for(int j=h[i];~j;j=road[j].ne) 
86         road[j].w += dist[i]-dist[road[j].to];
87     memcpy(dis,dist,sizeof dist);
88     for(int i=1;i<=n;i++)
89         printf("%lld\n",dijkstra(i));
90     return 0;
91 }