最短路扩展——分层图最短路

最短路扩展——分层图最短路
  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 typedef long long ll;
  9 const int maxv= 4000100;  /*记得开(n* k)的2倍*/
 10 const int maxe= 20000100; /*记得开(m* k)的4倍*/
 11 const int inf= 0x3f3f3f3f;
 12 
 13 struct ENode
 14 {
 15     int to;
 16     int w;
 17     int Next;
 18 };
 19 ENode edegs[maxe];
 20 int Head[maxv], tnt;
 21 void init()
 22 {
 23     memset(Head,-1,sizeof(Head));
 24     tnt = -1;
 25 }
 26 void Add_ENode(int u,int v,int w)
 27 {
 28     ++ tnt;
 29     edegs[tnt].to = v;
 30     edegs[tnt].w = w;
 31     edegs[tnt].Next = Head[u];
 32     Head[u] = tnt;
 33     ++ tnt;
 34     edegs[tnt].to = v;
 35     edegs[tnt].w = w;
 36     edegs[tnt].Next = Head[u];
 37     Head[u] = tnt;
 38 }
 39 
 40 int Dis[maxv];
 41 int vis[maxv]; //判断Dijkstra中是否已经查找过；
 42 struct cmpx
 43 {
 44     bool operator() (int &a, int &b) const
 45     {
 46         return Dis[a]- Dis[b]> 0;
 47     }
 48 };
 49 void Dijkstra(int s)
 50 {
 51     priority_queue<int, vector<int>, cmpx> q;
 52     memset(Dis, inf, sizeof(Dis));
 53     memset(vis,0,sizeof(vis));
 54     Dis[s]= 0;
 55     q.push(s);
 56 
 57     while (! q.empty())
 58     {
 59         int u= q.top();
 60         q.pop();
 61         if (vis[u]) continue;
 62         vis[u]= 1;
 63         for (int k= Head[u]; k!= -1; k= edegs[k].Next)
 64         {
 65             int v= edegs[k].to;
 66             if (! vis[v]&& Dis[v]> Dis[u]+ edegs[k].w)
 67             {
 68                 Dis[v]= Dis[u]+ edegs[k].w;
 69                 q.push(v);
 70             }
 71         }
 72     }
 73 }
 74 
 75 
 76 int main()
 77 {
 78     int n, m, s, t, k;
 79     while(~scanf("%d %d %d %d %d", &n, &m, &s, &t, &k))
 80     {
 81         init();
 82         while( m--)
 83         {
 84             int u, v, w;
 85             scanf("%d %d %d",&u, &v, &w);
 86             for(int i = 0; i <= k; i++)
 87             {
 88                 Add_ENode(u + i * n, v + i * n, w);
 89                 Add_ENode(v + i * n, u + i * n, w);
 90                 if(i != k)
 91                 {
 92                     Add_ENode(u + i * n, v + (i + 1) * n, 0);
 93                     Add_ENode(v + i * n, u + (i + 1) * n, 0);
 94                 }
 95             }
 96         }
 97         Dijkstra(s);
 98         int ans = inf;
 99         for(int i = 0; i <= k; i++)
100         {
101             ans = min(ans, Dis[t + i * n]);
102         }
103         printf("%d
",ans);
104     }
105 }
View Code