题解 P2832 【行路难】

[题目传送门](https://www.luogu.org/problem/P2832) 给出一种保证正确但复杂度玄学的算法。 使用dijkstra，开一个$dis$数组，$dis_{i,j}$表示从1到$i$，共经过$j$条边的最小距离，但容易发现这样内存会炸，于是可以考虑用map，然后就可以愉快dijkstra了，跑的时候顺便记录一下前驱。 但是这样只有52分，还得加一个剪枝，记录一下从1到$i$的最短距离和这个最短距离共经过了几条边，如果当前的距离大于这个最短距离，当前经过的边数也大于这个边数，当前状态就一定不是最优的，~~再卡卡常，开开O2，就过了~~，最慢的点跑了981ms。 代码： ``` #include <bits/stdc++.h> using namespace std; namespace io { #define SIZ (1 << 21 | 1) #define gc() (iS == iT ? (iT= (iS= ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++) #define out() \ fwrite(obuff, 1, oS - obuff, stdout); \ oS= obuff; char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS= obuff, *oT= oS + SIZ - 1, fu[110], c; int fr; template <class Type> inline void read(Type &x) { x= 0; Type y= 1; for(c= gc(); (c > '9' || c < '0') && c != '-'; c= gc()) ; c == '-' ? y= -1 : x= (c & 15); for(c= gc(); c >= '0' && c <= '9'; c= gc()) x= x * 10 + (c & 15); x*= y; } template <class Type> inline void print(Type x, char text= '\n') { if(x < 0) *oS++= '-', x*= -1; if(x == 0) *oS++= '0'; while(x) fu[++fr]= x % 10 + '0', x/= 10; while(fr) *oS++= fu[fr--]; *oS++= text; out(); } } using io::print; using io::read; #define N 10001 #define M 200001 int n, m, head[N], cnt, ans= 2147483647, mi, stac[N], top, a1[N], a2[N]; struct sb//链式前向星存边 { int a, b, c; inline sb(int x= 0, int y= 0, int z= 0) { a= x, b= y, c= z; } } e[M]; inline void add(int a, int b, int c)//建边 { e[++cnt]= sb(head[a], b, c), head[a]= cnt; } struct sb2//放到优先队列里的东西 { int a, b, c; inline sb2(int x= 0, int y= 0, int z= 0) { a= x, b= y, c= z; } inline bool operator<(const sb2 &y) const { return b > y.b; } }; priority_queue<sb2> q; struct sb3//放到map里的东西 { int a, b; inline sb3(int x= 0, int y= 0) { a= x, b= y; } inline bool operator<(const sb3 &y) const { return a < y.a || (a == y.a && b < y.b); } }; map<sb3, int> dis, pre;//距离，前驱 map<sb3, bool> vis;//dijkstra的vis数组 signed main() { #ifndef ONLINE_JUDGE freopen("testdata.in", "r", stdin); freopen("testdata.out", "w", stdout); #endif read(n), read(m); for(int i= 1, a, b, c; i <= m; i++) read(a), read(b), read(c), add(a, b, c);//建边 memset(a1, 0x7f, sizeof(a1));//初始化 q.push(sb2(1, 0, 0)); dis[sb3(1, 0)]= 0; while(!q.empty())//跑dijkstra { sb2 kkk= q.top(); q.pop(); if(vis[sb3(kkk.a, kkk.c)] || kkk.c == n) continue;//如果已经访问过就continue，同时如果已经经过了n个点接下来就会重复经过点，肯不是最优的，也continue if(kkk.b >= a1[kkk.a] && kkk.c > a2[kkk.a]) continue;//上面讲的剪枝 vis[sb3(kkk.a, kkk.c)]= 1; if(kkk.a == n)//记录答案 { if(ans > kkk.b) { ans= kkk.b, mi= kkk.c; } } for(int i= head[kkk.a]; i; i= e[i].a) { int xxx= kkk.b + e[i].c + kkk.c; sb3 xx(e[i].b, kkk.c + 1); map<sb3, int>::iterator it= dis.find(xx); if(it == dis.end() || (*it).second > xxx)//更新dis { dis[xx]= xxx; pre[xx]= kkk.a; if(xxx < a1[e[i].b])//更新从1到i的最短路径 { a1[e[i].b]= xxx; a2[e[i].b]= kkk.c + 1; } else if(xxx == a1[e[i].b] && kkk.c + 1 < a2[e[i].b]) a2[e[i].b]= kkk.c + 1; q.push(sb2(e[i].b, dis[xx], kkk.c + 1)); } } } print(ans); for(sb3 i= sb3(n, mi); i.b >= 0; i= sb3(pre[i], i.b - 1)) stac[++top]= i.a;//记录路径 for(int i= top; i; i--) print(stac[i], ' '); } ```