【CODEVS 1021】玛丽卡 SPFA+枚举

63 阅读 0 评论 42 点赞

我是靠谱客的博主开放信封，最近开发中收集的这篇文章主要介绍【CODEVS 1021】玛丽卡 SPFA+枚举，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

好久没有写过解题报告了，准确的说是好久没有写过代码了。作为一只OI届的咸鱼，回去搞文化课也仍然是一只咸鱼。期末考炸了，写代码的能力也一直下降。。。。现在还是找出时间写一下代码，为NOIP2016做准备。有时间要多写写代码。
CODEVS— 1021:http://codevs.cn/problem/1021/
题目描述 Description
麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。（其实我不想帮助麦克，我更想帮助玛丽卡抓住麦克然后弄死他。）
因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

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

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

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

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

输入描述 Input Description
第一行有两个用空格隔开的数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分钟内是就能通过。

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

样例输出 Sample Output

题解

这个题目问的是怎么让最短路最长，第一次我看见了之后以为是二分，后来发现因为只有一条最短路，所以不需要二分。直接枚举最短路上的每一条路不允许走，然后跑SPFA。就可以了。
代码

/*
作者:WZH
题目:p1021 玛丽卡
*/
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAXN = 1000000,INF = 1000000;

int head[MAXN],e = 1,ans,N,M,d[MAXN],fa[MAXN];
bool inq[MAXN];
queue<int>q;

struct node{
    int v,c,next,FA;
}edge[MAXN*11];

inline void addedge(int u,int v,int c){
    edge[e] = {v,c,head[u],u};head[u] = e++;
    edge[e] = {u,c,head[v],v};head[v] = e++;
}

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' ||  '9'< ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void init(){
    N = read();M = read();
    int u,v,c;

    for(int i = 1;i <= M;i++){
        u = read();v = read();c = read();
        addedge(u,v,c);
    }

}

inline void spfa(int u){

    for(int i = 1;i <= N;i++) d[i] = INF;
    d[u] = 0;inq[u] = true;q.push(u);

    while(!q.empty()){
        int x = q.front();q.pop();inq[x] = false;
        for(int i = head[x];i;i = edge[i].next){
            int v = edge[i].v,c = edge[i].c ;
            if(d[v] > d[x] + c){
                d[v] = d[x] + c;
                fa[v] = i;
                if(!inq[v]) {q.push(v);inq[v] = true;}
            }
        }
    }

}

inline void spfa_1(int u,int from ,int to){ 
    for(int i = 1;i <= N;i++) d[i] = INF;
    d[u] = 0;inq[u] = true;q.push(u); 
    while(!q.empty()){
        int x = q.front();q.pop();inq[x] = false;
        for(int i = head[x];i;i = edge[i].next){
            int v = edge[i].v,c = edge[i].c ;  
            if(d[v] > d[x] + c){
                if((x == from && v == to) || (v == from && x == to)) continue;
                d[v] = d[x] + c;
                if(!inq[v]) {q.push(v);inq[v] = true;}
            }
        }
    }
}

int main(){
    init();

    spfa(1);
    ans = max(d[N],ans);
    for(int i  = fa[N];i;i = fa[edge[i].FA])
    {
        spfa_1(1 ,edge[i].FA ,edge[i].v); 
        ans = max(d[N],ans);
    }
    printf("%dn",ans);
    return 0;
}