题解：P1811 最短路

luoxb · 2025-07-17 20:49:14 · 题解

题意分析

题面本身已经很清晰了，即考虑限制条件下的单源最短路问题，注意无向图，以及观察样例可知可以走回头路。

算法分析

部分 1

单源最短路肯定考虑 dijkstra 算法，但是限制条件如何体现呢？

实际上，dijkstra 算法虽然不是 DP 而是贪心，但是其与 DP 有着不小的相似性，其中最重要的就是 状态转移。

普通的 dijkstra 算法包含 3 个容器，分别是记录距离状态的 dist，记录松弛状态的 confirm 以及一个堆。

那么回到题目所说的限制条件，重新翻译一下就是：

若当前节点为 B，上一个节点为 A，目标节点为 C，则这一次转移不能进行

也就是说我们需要记录每个节点的上一个节点的状态，考虑到不同的转移，每种合法的转移方式都对应了不同的距离，于是给 dist 数组和 confirm 数组多开一维，含义分别如下：

dist [i][j]：在节点 j，上一个节点为 i 时到原点的最小距离
confirm [i][j]：在节点 j，上一个节点为 i 时是否已经确认答案正确

至此，只需要在读入时用 map 储存节点 B 对应的 A 和 C，就可以在尝试松弛时检查转移是否合法，剩下的部分即为普通的 dijkstra 算法。

部分 2

但是至此只完成了题目的第一问，路径如何记录呢？

其实记录路径有很多种方法，但是由于题目有时必须走回头路，所以我用了 string 来进行储存，在每次搜到终点时记录即可。

复杂度分析

dijkstra 复杂度： O(n\log n)。
路径记录最差复杂度： O(nm)。
综合来看最差即为 O(nm) 可以通过本题。

实现

#include<bits/stdc++.h>
using namespace std;

const int MAX = 3e3+5;

int n,m,k,a,b,c;
int dist[MAX][MAX],confirm[MAX][MAX];

vector<int> g[MAX];

struct Node{
    int u,v,d;
    string path;
    bool operator < (Node t)const{
        return d>t.d;
    }
    bool operator == (Node t)const{
        return u == t.u && v == t.v;
    }
}ans;
map<int,Node> restrict;
priority_queue<Node> q;

string concat(int i,string s){
    return s+" "+to_string(i);
}

void dijkstra(int u){
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++) dist[u][i] = 0;
    ans.d = 0x3f3f3f3f;

    q.push({u,u,0,to_string(u)});

    while(q.size()){
        Node top = q.top();
        q.pop();

        int u = top.v;

        if (confirm[top.u][u]) continue;
        confirm[top.u][u] = true;

        for (int i:g[u]){
            if (restrict[u] == (Node){top.u,i}) continue;
            if (dist[u][top.u] + 1 < dist[i][u]){
                dist[i][u] = dist[u][top.u] + 1;
                Node node = (Node){u,i,dist[i][u],concat(i,top.path)};
                q.push(node);
                if (i == n && node.d<ans.d){
                    ans = node;
                } 
            }
        }
    }
}

int main(){
    cin>>n>>m>>k;
    for (int y=0;y<m;y++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int y=0;y<k;y++){
        cin>>a>>b>>c;
        restrict[b] = (Node){a,c};
    }

    dijkstra(1);

    int f = INT_MAX;
    for(int i=1;i<=n;i++) f = min(f,dist[n][i]);
    cout<<f<<'\n';
    cout<<ans.path;
    return 0;
}

后记

首先由于边权固定为 1，这题肯定是不需要用 dijkstra 的。其次，对于同一个 B 可能有多个限制，目前的代码是无法体现的，不过数据很水，遂罢之。