【分层图最短路,dijstra】P2939 [USACO09FEB]改造路Revamping Trails


 1 #include<iostream> 2 #include<string> 3 #include<queue> 4 #include<stack> 5 #include<vector> 6 #include<map> 7 #include<cstdio> 8 #include<cstdlib> 9 #include<algorithm> 10 #include<set> 11 #include<list> 12 #include<iomanip> 13 #include<cstring> 14 #include<cmath> 15 #include<limits> 16 using namespace std; 17  18 #define au auto 19 #define debug(i) cout<<"<debug> "<<i<<"<\debug>"<<endl 20 #define mfor(i,a,b) for(register int i=(a);i<=(b);i++) 21 #define mrep(i,a,b) for(register int i=(a);i>=(b);i--) 22 #define LLL __int128 23 #define Re register 24 #define il inline 25 #define mem(a,b) memset(a,(b),sizeof(a)) 26 typedef pair<int, int> intpair; 27 typedef long long int LL; 28 const int INF = 0x3f3f3f3f; 29 const long long int INFLL = 0x3f3f3f3f3f3f3f3f; 30  31 int cnt; 32 const int maxn = 5000010; 33 int n, m, k; 34  35 struct Edge 36 { 37 int u, nxt; 38 int w; 39 }e[maxn]; 40  41 int head[maxn]; 42  43 void add(int a, int b, int w) 44 { 45 e[++cnt].u = b; 46 e[cnt].nxt = head[a]; 47 head[a] = cnt; 48 e[cnt].w = w; 49 } 50  51 typedef struct 52 { 53 bool operator ()(const intpair& a, const intpair& b)const 54  { 55 return a.second > b.second; 56  } 57 }cmp; 58  59 int dis[maxn]; 60 bool vis[maxn]; 61 priority_queue<intpair, vector<intpair>, cmp>q; 62  63 void dijstra(int x) 64 { 65 mem(dis, 0x3f); 66 mem(vis, false); 67 dis[x] = 0; 68  q.push(intpair(x, dis[x])); 69 while (!q.empty()) 70  { 71 intpair t = q.top(); 72  q.pop(); 73 if (vis[t.first]) continue; 74 vis[t.first] = true; 75 for (int i = head[t.first]; i != -1; i = e[i].nxt) 76  { 77 int u = e[i].u; 78 int w = e[i].w; 79 if (!vis[u] && dis[u] > t.second + w) 80  { 81 dis[u] = t.second + w; 82  q.push(intpair(u, dis[u])); 83  } 84  } 85  } 86 } 87  88 int main() 89 { 90 cin >> n >> m >> k; 91 mem(head, -1); 92 mfor(i, 1, m) 93  { 94 int a, b, c; 95 cin >> a >> b >> c; 96  add(a, b, c); 97  add(b, a, c); 98 mfor(j, 1, k) 99  {100 add(j * n + a, j * n + b, c);101 add(j * n + b, j * n + a, c);102 add((j - 1) * n + a, j * n + b, 0);103 add((j - 1) * n + b, j * n + a, 0);104  }105  }106 dijstra(1);107 int ans = dis[n];108 mfor(i, 1, k)109  {110 ans = min(ans, dis[i * n + n]);111  }112 cout << ans;113 return 0;114 }

View Code

 

相关文章