[IOI2011]crocodile

zhouhuanyi · 2020-01-21 14:55:42 · 题解

这题没有题解，我就来发一篇。

链接：https://www.luogu.com.cn/problem/P5845

题目描述:给定出发点s与k个终点，有一个鳄鱼门卫可以在每一轮堵住一条边，求最坏情况下走到终点要多长时间。

题解:从出发点像终点考虑十分复杂，不妨从终点向出发点考虑，由于鳄鱼门卫会挡住一条边，所以从一个与终点相邻的点到终点的最短路径一定会被挡住，只能走次短路。由于到该点的路是次短路，所以我们只能用次短路更新。以此类推，每个点每一次用到自己的次短路去扩展即可。

#include<iostream>
#include<queue>
using namespace std;
struct node
{
    int v,data,nxt;
};
node edge[10000001];
struct reads
{
    int num,data;
    bool operator < (const reads &a)const
    {
        return data>a.data;
    }
};
reads tmp;
int head[10000001],len;
int n,m,dis[10000001],dis2[10000001];
bool used[10000001];
priority_queue<reads>q;
void add(int x,int y,int z)
{
    edge[++len].v=y;
    edge[len].data=z;
    edge[len].nxt=head[x];
    head[x]=len;
    return;
}
reads make_reads(int x,int y)
{
    tmp.num=x;
    tmp.data=y;
    return tmp;
}
void dijkstra()
{
    int top;
    while (!q.empty())
    {
        top=q.top().num;
        q.pop();
        if (used[top])
            continue;
        used[top]=1;
        for (int i=head[top];i>0;i=edge[i].nxt)
        {
            if (dis[edge[i].v]>dis2[top]+edge[i].data)
            {
                dis2[edge[i].v]=dis[edge[i].v];
                dis[edge[i].v]=dis2[top]+edge[i].data;
                q.push(make_reads(edge[i].v,dis2[edge[i].v]));
            }
            else if (dis2[edge[i].v]>dis2[top]+edge[i].data)
            {
                dis2[edge[i].v]=dis2[top]+edge[i].data;
                q.push(make_reads(edge[i].v,dis2[edge[i].v]));
            }
        }
    }
    cout<<dis2[0]<<endl;
    return;
}
int main()
{
    int k,x,y,z;
    cin>>n>>m>>k;
    for (int i=0;i<=n-1;++i)
        dis[i]=dis2[i]=1e9;
    for (int i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for (int i=1;i<=k;++i)
    {
        cin>>x;
        dis[x]=dis2[x]=0;
        q.push(make_reads(x,0));
    }
    dijkstra();
    return 0;
}