题解：P1811 最短路

· · 题解

题目分析

求 1 \sim n 的最短路径，并且有 K 个约束，表示不能存在 a \to b \to c 的走法。

观察到 n 很小，可以设计类似 dp 的状态转移，由于有环，需要最短路辅助。

设 dp_{i,j} 表示走到 i 点且上一个点走的是 j 的最短距离，将 dp 数组看成最短路中的 dis 数组，有转移方程：

dis_{v,u}=\min dis_{u,pred} + 1

其中 (pred,u,v) 是合法的三元组。

跑一遍 dijkstra 即可。

时间复杂度：总状态数是 \Theta(n^2) 的，堆优化 dijkstra 复杂度为 \Theta(n^2 \log n)。

注意此题略卡空间。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
using namespace __gnu_pbds;
const int INF=0x3f3f3f3f;
inline int read()
{
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=3005;
umap<int,umap<int,umap<int,int>>> f;
int n,m,K;
vint G[N];
int dis[N][N],vis[N][N];
pii pre[N][N];
struct state
{
    int u,pred,dis;
    bool operator <(const state &b)const
    {
        return dis>b.dis;
    }
};
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<state> Q;
    dis[s][0]=0;
    Q.push({s,0,0});
    while(!Q.empty())
    {
        auto temp=Q.top();Q.pop();
        int u=temp.u,pred=temp.pred;
        if(vis[u][pred]) continue;
        vis[u][pred]=1;
        for(int v:G[u])
        {
            if(f.find(pred)!=f.end()&&f[pred].find(u)!=f[pred].end()&&f[pred][u].find(v)!=f[pred][u].end()) continue;
            if(dis[v][u]>dis[u][pred]+1) dis[v][u]=dis[u][pred]+1,pre[v][u]=make_pair(u,pred),Q.push({v,u,dis[v][u]});
        }
    }
}
void print(int u,int pred)
{
    if(!u) return;
    print(pre[u][pred].first,pre[u][pred].second);
    cout<<u<<" ";
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    n=read(),m=read(),K=read();
    for(int i=1,u,v;i<=m;++i)
    {
        u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    for(int i=1,a,b,c;i<=K;++i)
    {
        a=read(),b=read(),c=read();
        f[a][b][c]=1;
    }
    dijkstra(1);
    int pos=min_element(dis[n]+1,dis[n]+n+1)-dis[n];
    cout<<dis[n][pos]<<endl;
    print(n,pos);
    cout<<endl;
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}