poj3255Roadblocks

Roadblocks

题意:

给你n个点和r个边，求次短路。

思路：

考虑一下次短路v的条件，第一种是到u的最短路+d（u，v），第二种是到u的次短路+d（u，v）。
因此，只需要维护一下最短路和次短路就可以了，

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define ll long long
using namespace std;
const double PI = acos(-1.0);
const int N = 5e3 + 10;
const int mod = 998244353;
////////////////////////////////
struct node
{
    int to;
    int cost;
    bool operator<(const node &r) const
    {
        return cost > r.cost;
    }
};
vector<node> e[N];
int dist1[N];
int dist2[N];
int main()
{
    int n, m;
    while (cin>>n>>m)
    {
        for (int i = 0; i < m; i++)
        {
            node cur;
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            cur.to = v;
            cur.cost = w;
            e[u].pb(cur);
            cur.to = u;
            e[v].pb(cur);
        }
        fill(dist1 + 1, dist1 + n + 1, inf);
        fill(dist2 + 1, dist2 + n + 1, inf);
        dist1[1] = 0;
        node cur;
        cur.to = 1, cur.cost = 0;
        priority_queue<node> q;
        q.push(cur);
        while (!q.empty())
        {
            node tmp = q.top();
            q.pop();
            int v = tmp.to, d = tmp.cost;
            if (dist2[v] < d)
                continue;
            for (int i = 0; i < e[v].size(); i++)
            {
                node now = e[v][i];
                int d2 = now.cost + d;
                if (d2 < dist1[now.to])
                {
                    swap(dist1[now.to], d2);
                    node cur;
                    cur.cost = dist1[now.to];
                    cur.to = now.to;
                    q.push(cur);
                }
                if (dist2[now.to] > d2 && d2 > dist1[now.to])
                {
                    dist2[now.to] = d2;
                    node cur;
                    cur.to = now.to;
                    cur.cost = dist2[now.to];
                    q.push(cur);
                }
            }
        }
        cout << dist2[n] << endl;
    }
    return 0;
}