题解 P2865 【[USACO06NOV]路障Roadblocks】

· · 题解

本题对最短路要求有很好的理解，在用dijkstra时候，就直接更新次短路，用d[]代表最短路，用d2[]代表次短路，然后在松弛的时候同时更新两个数组，要判断三个条件 （u是当前考虑的点，v是与u有边相连的点，d(u,v)表示从u到v的边长） 1.如果dis[v]>dis[u]+d(u,v)，则更新dis[v] 2.如果dis[v]<dis[u]+d(u,v)（不能取等，否则dis2[v]和dis[v]可能相等）且dis2[v]>dis[u]+d(u,v)，则更新dis2[v] 3.如果dis2[v]>dis2[u]+d(u,v)，则更新dis2[v]（显然，如果2成立，更新后dis2[v]=dis[u]+d(u,v)<dis2[u]+d(u,v)，即3一定不成立） 如果上述三个条件中有任意一个成立，则将v入队。 本题提交了很多次才过，误区在于：满足上述3个条件将v入队列，v的长度一定是d[v]而不是d2[v](尽管触发第2个和第3个条件），这个地方WA 了很久。 另外大家都用链式前向星来建图，我还是习惯邻接表（vector），感觉也没啥影响。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge
{
    int to;
    int cost;
};
struct sa
{
    int id;
    int dis;
    bool operator<(const sa &b) const
    {
        return dis>b.dis;
    }

};
vector<edge> g[5001];
int d[5001],d2[5001];
priority_queue<sa> vis;
int n,m;
int dijkstra()
{
for(int i=1;i<=n;i++)
        d[i]=inf,d2[i]=inf;
    d[1]=0;
    vis.push((sa){1,0});
    while(!vis.empty())
    {
        sa tp=vis.top();
        vis.pop();
        int u=tp.id;
        int du=tp.dis;
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].to;
            int w=g[u][i].cost;
            int flag=0;
            if (du+w<d[v])
                d[v]=du+w,flag=1;
            if (du+w>d[v]&&du+w<d2[v])
                d2[v]=du+w,flag=1;
            if (d2[u]+w<d2[v])
                d2[v]=d2[u]+w,flag=1;
            if (flag==1)
            vis.push((sa){v,d[v]});

        }

    }

return 0;
}
int main()
{
    int a,b,c;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        g[a].push_back((edge){b,c});
        g[b].push_back((edge){a,c});
    }
    dijkstra();

    cout<<d2[n]<<endl;
    return 0;
}