Roadblocks

转载请注明出处：https://blog.csdn.net/Robertlyp/article/details/93485855

题见：Roadblocks
Solution
次短路径
先用Dijkstra求1和n的最短路
对于每条边 (x, y, z)：
$Ans=Min\left\{dis{t}_1\right[x]+z+dis{t}_n[y\left]\right\}\left(dis{t}_1\right[x]+z+dis{t}_n[y]\>dis{t}_1[n\left]\right)$Ans=Min{dist1​[x]+z+distn​[y]}(dist1​[x]+z+distn​[y]>dist1​[n])

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

int n, r;
int b1[5010], bn[5010], d1[5010], dn[5010];
priority_queue<pair<int, int> > q;
vector<pair<int, int> > edge[5010];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> r;
    memset(d1, 0x3f, sizeof d1);
    memset(dn, 0x3f, sizeof dn);
    d1[1] = dn[n] = 0;
    for (int i = 1; i <= r; i++)
    {
        int A, B, D;
        cin >> A >> B >> D;
        edge[A].push_back(make_pair(B, D));
        edge[B].push_back(make_pair(A, D));
    }
    q.push(make_pair(0, 1));
    while (q.size())
    {
        int x = q.top().second; q.pop();
        if (b1[x]) continue;
        b1[x] = 1;
        for (int i = 0; i < edge[x].size(); i++)
        {
            int y = edge[x][i].first, z = edge[x][i].second;
            if (d1[y] > d1[x] + z)
            {
                d1[y] = d1[x] + z;
                q.push(make_pair(-d1[y], y));
            }
        }
    }
    q.push(make_pair(0, n));
    while (q.size())
    {
        int x = q.top().second; q.pop();
        if (bn[x]) continue;
        bn[x] = 1;
        for (int i = 0; i < edge[x].size(); i++)
        {
            int y = edge[x][i].first, z = edge[x][i].second;
            if (dn[y] > dn[x] + z)
            {
                dn[y] = dn[x] + z;
                q.push(make_pair(-dn[y], y));
            }
        }
    }
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < edge[i].size(); j++)
        {
            int dis = d1[i] + edge[i][j].second + dn[edge[i][j].first];
            if (dis > d1[n] && dis < ans)
                ans = dis;
        }
    printf("%d\n", ans);

    return 0;
}