题解 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], ' ');
}