【codevs1021】玛丽卡，以前屯着的最短路

60 阅读 0 评论 40 点赞

我是靠谱客的博主甜美背包，最近开发中收集的这篇文章主要介绍【codevs1021】玛丽卡，以前屯着的最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门
写在前面：以前屯着的一个最短路，感觉有点恶心o_O
思路：最初用的堆优化dijskra+邻接矩阵，结果T了3组，就放在那里了。现在捡起来用了SPFA+邻接表枚举所有边，T了2组，然后想到先求出最短路，枚举最短路径上的边就可以了，但是调了半天都不对，最后发现是循环变量名打错了……
代码：

#include<bits/stdc++.h>
using namespace std;
int tot,n,m,ans;
int first[1010],dis[1010],up[1010],e[1010];//up记录最短路径上每个点的入度边,e则是记录最短路径上的边
bool flag[1010];
struct os
{
    int fa,son,next,w;
}a[1000010];
void add(int x,int y,int z)
{
    a[++tot].fa=x;
    a[tot].son=y;
    a[tot].w=z;
    a[tot].next=first[x];
    first[x]=tot;
}
main()
{
    scanf("%d%d",&n,&m);
    queue<int> q;
    int x,y,z;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    //读入
    memset(dis,63,sizeof(dis));
    dis[1]=0;
    q.push(1);
    flag[1]=1;
    while (!q.empty())
    {
        int t=q.front();
        flag[t]=0;
        q.pop();
        for (int i=first[t];i;i=a[i].next)
        {
            int p=a[i].son;
            if (dis[t]+a[i].w<dis[p])
            {
                dis[p]=dis[t]+a[i].w;
                up[p]=i;
                if (!flag[p]) q.push(p),flag[p]=1;
            }
        }
    }
    //SPFA求最短路
    for (int i=up[n];i;i=up[a[i].fa]) 
    e[++e[0]]=i;
    //从n倒着走，求出最短路径并记录在e中
    for (int i=1;i<=e[0];i++)
    {
        int k=a[e[i]].w;
        a[e[i]].w=0x7fff;
        if (e[i]%2==0) a[e[i]-1].w=0x7fff;
        else a[e[i]+1].w=0x7fff;//这里也可以用xor，不过最初的路径编号要为0
        memset(dis,63,sizeof(dis));
        dis[1]=0;
        q.push(1);
        flag[1]=1;
        while (!q.empty())
        {
            int t=q.front();
            flag[t]=0;
            q.pop();
            for (int j=first[t];j;j=a[j].next)
            {
                int p=a[j].son;
                if (dis[t]+a[j].w<dis[p])
                {
                    dis[p]=dis[t]+a[j].w;
                    if (!flag[p]) q.push(p),flag[p]=1;
                }
            }
        }
        if (dis[n]<0x7fff) ans=max(ans,dis[n]);
        a[e[i]].w=k;
        if (e[i]%2==0) a[e[i]-1].w=k;
        else a[e[i]+1].w=k;
    }
    //去掉最短路径上的边后再求最短路就行了
    printf("%d",ans);
}