Processing math: 100%

【题解】图论最短路径 玛丽卡

于由XZYQvQ发布

题目描述

麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。

玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。

编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间 (用分钟表示)。

输入输出格式

输入格式：

第一行有两个用空格隔开的数 N 和 M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用数字 1 至 N 标识，麦克在城市 1 中，玛丽卡在城市 N 中。

接下来的 M 行中每行包含三个用空格隔开的数 A，B 和 V。其中 1≤A，B≤N，1≤V≤1000。这些数字表示在 A 和城市 B 中间有一条双行道，并且在 V 分钟内是就能通过。

输出格式：

输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。

输入样例：

5 7

1 2 8

1 4 10

2 3 9

2 4 10

2 5 1

3 4 7

3 5 10

输出样例：

27

思路：跑一遍最短路，求出最短路径，然后依次删掉最短路径上的路，每次删一条，删了以后再跑最短路，求出最短时间，然后补上刚刚删掉的那条路。等每个最短路径上的路都被删过一次后，输出刚刚求出的最短时间中值最大的那个。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct edge{int p,v;};
typedef vector<edge> vn;
const int inf=100000000;
int n,m,dis[1001],pre[1001],ans,sv;
bool book[1001];
vn l[1001];vn::iterator pree[1001];edge np;
void spfa()
{
    queue<int> que;
    for(int i=1;i<=n;i++)dis[i]=inf,book[i]=0;
    dis[1]=pre[1]=0,book[1]=1,que.push(1);
    while(!que.empty())
    {
        int f=que.front();
        for(vn::iterator i=l[f].begin();i!=l[f].end();i++)
            if(dis[i->p]>dis[f]+i->v)
            {
                dis[i->p]=dis[f]+i->v,pre[i->p]=f;pree[i->p]=i;
                if(!book[i->p]){que.push(i->p);book[i->p]=1;}
            }
        que.pop(),book[f]=0;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    while(m--){int a;cin>>a>>np.p>>np.v;l[a].push_back(np);swap(a,np.p);l[a].push_back(np);}
    spfa();
    vector<vn::iterator> pass;
    int q=n;
    while(q!=1){pass.push_back(pree[q]);q=pre[q];}
    for(unsigned int i=0;i<pass.size();i++){sv=pass[i]->v,pass[i]->v=inf;spfa();ans=max(ans,dis[n]);pass[i]->v=sv;}
    cout<<ans;
    return 0;
}
C++
Copy
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

18 条评论

zhouzhendong · 2018年7月21日 7:03 下午

左侧栏更新博客园有延时

回复

    XZYQvQ · 2018年7月21日 7:05 下午

    QwQ 这么有意思 QwQ
    您为啥不考虑自己搭一个 Blog 呢您这么 StrongOrz（强行尬聊+拉你入坑.jpg）

    回复

      zhouzhendong · 2018年7月21日 7:07 下午

      搭这个东西挺耗时间的吧……
      搭不动啊
      我觉得博客园挺好的……

      回复

        XZYQvQ · 2018年7月21日 7:15 下午

        emmm… 海星啊
        我也就一共浪费了几个星期的样子吧 (MMP)

        回复

zhouzhendong · 2018年7月21日 7:01 下午

您才是 fake……

回复

zhouzhendong · 2018年7月21日 6:56 下午

我写 dij+heap 过了

回复

    zhouzhendong · 2018年7月21日 6:57 下午

    我说 NOI2018DayT1 同步赛

    回复

    XZYQvQ · 2018年7月21日 6:57 下午

    emmmmmm…So….
    OrzDalao 加友联么？OvO

    回复

      zhouzhendong · 2018年7月21日 6:58 下午

      可以啊（我很菜的）

      回复

        XZYQvQ · 2018年7月21日 7:00 下午

        Orz Don’t be fAke Orz
        您的友联已经给您加上了 Orz
        详见 “传送门”（疯狂扩列中 QwQ 不会 SEO 啊怎么办 QwQ）

        回复

zhouzhendong · 2018年7月21日 6:55 下午

不过 spfa 复杂度上限的确是 O(n2)的

回复

zhouzhendong · 2018年7月21日 5:55 下午

妙啊，O(N^3) 过 1000。

回复

    XZYQvQ · 2018年7月21日 6:51 下午

    怎么就成 O(N^3) 了，Spfa 复杂度咋就成 O(N^2) 了。。。

    回复

      zhouzhendong · 2018年7月21日 6:52 下午

      上面的那个不是本人

      回复

      zhouzhendong · 2018年7月21日 6:55 下午

      不过 spfa 复杂度上限的确是 O(n2)的

      回复

        XZYQvQ · 2018年7月21日 6:56 下午

        emmmm 对于这题貌似是的。。。QwQ
        Orz 突然发现 LaTex 没法在评论区使用我也不知道发生了什么。。。
        那评论就不用 LaTex 吧嘿嘿嘿

        回复

    XZYQvQ · 2018年7月21日 6:54 下午

    不过说起来 Spfa 以后是不怎么敢用了，这次 NOID1T1 算是恶心到我了。。。

    回复

回复 XZYQvQ 取消回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注