题解 P2832 【行路难】
pzc2004
2019-12-16 13:24:32
[题目传送门](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], ' ');
}
```
![](https://www.luogu.org/images/congratulation.png)