最短路问题

佚名 6年前 (2019-05-06) 随笔 1798人围观抢沙发百度已收录

反向边思想

分层图

 1 /*
 2     分层图：（还有另一种方法：就是先这样一下，再那样...我不会
 3             建第一层图时，随便多cope建 k 层相同的图，再将从上到下相邻的各图按照某一特殊权值连接（实际上是连点 
 4             遍历时基本没变化，只不过有可能需要注意把那个终点也连一下， 
 5 */
 6 #include<cstdio>
 7 #include<queue>
 8 using namespace std;
 9 
10 const int MAXN = 1200000;
11 const int MAXM = 6660000;
12 const int INF = 1000003647;
13 
14 int n,m,k,cnt,s,t;
15 int vis[MAXN], dis[MAXN],head[MAXN];
16 
17 struct node{
18     int id,dis;
19     node(int id = 0, int dis = 0) : id(id), dis(dis) {}
20     bool operator < (const node &xx) const {
21         return dis > xx.dis ;
22     }
23 }; 
24 
25 priority_queue <node> q;
26 
27 struct edge{
28     int y,val,next;
29 }e[MAXM];
30 
31 void add_edge(int x, int y, int val) {
32     e[++cnt].y = y;
33     e[cnt].next = head[x];
34     e[cnt].val = val;
35     head[x] = cnt;
36 }
37 
38 void dijkstra() {
39     int tmp2 = n*(k+1);
40     for(int i = 1; i <= tmp2; i++) dis[i] = INF;
41     q.push(node(s,0));
42     dis[s] = 0;
43     while(!q.empty() ) {
44         node tmp = q.top() ;
45         q.pop() ;
46         int now = tmp.id ;
47         if(vis[now]) continue;
48         vis[now] = 1;
49         for(int i = head[now]; i; i = e[i].next ) {
50             int y = e[i].y;
51             if(dis[y] > tmp.dis + e[i].val ) {
52                 dis[y] = tmp.dis + e[i].val ;
53                 q.push(node(y,dis[y])); 
54             }
55         }
56     }
57 } 
58 
59 
60 int main() {
61     scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
62     s++,t++;//题目是从0开始的(这只是个人喜好... 
63     int x,y,z;
64     for(int i = 1; i <= m; i++) {
65         scanf("%d%d%d",&x,&y,&z);
66         x++,y++;
67         add_edge(x, y, z);
68         add_edge(y, x, z);//在第1层加边（i）完成 
69         //成败在此一举 
70         for(int j = 1; j <= k; j++) {//一共有“k+1”层 
71         
72             add_edge(x+j*n, y+j*n, z);//cope第一层中的边i到各层(第j+1层)
73             add_edge(y+j*n, x+j*n, z);
74             add_edge(x+(j-1)*n, y+j*n, 0);//将第j层的x与第j+1层的y相连
75             add_edge(y+(j-1)*n, x+j*n, 0);//将第j层的y与第j+1层的x相连
76             //此题中分层图间的特殊权值是0 
77         }
78     }
79         //处理终点，不然在这题中可能会出现免费次数没用完就已经到达了终点，这样就不能直接写dis[t=n*k]了 
80         for(int i = 1; i <= k; i++) add_edge(t+(i-1)*n, t+i*n, 0);
81         dijkstra();
82         printf("%d",dis[t+n*k]);
83 }
84 /*5 6 1
85 0 4
86 0 1 5
87 1 2 5
88 2 3 5
89 3 4 5
90 2 3 3
91 0 2 100*/