HDU 3986 Harry Potter and the Final Battle

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3986

题目：

Harry Potter and the Final Battle
Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1139    Accepted Submission(s): 359

Problem Description
The final battle is coming. Now Harry Potter is located at city 1, and Voldemort is located at city n. To make the world peace as soon as possible, Of course, Harry Potter will choose the shortest road between city 1 and city n. But unfortunately, Voldemort is so powerful that he can choose to destroy any one of the existing roads as he wish, but he can only destroy one. Now given the roads between cities, you are to give the shortest time that Harry Potter can reach city n and begin the battle in the worst case.

Input
First line, case number t (t<=20).
Then for each case: an integer n (2<=n<=1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0< m <=50000). Following m lines, each line with three integer u, v, w (u != v,1 <=u, v<=n, 1<=w <1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities.

Output
Each case per line: the shortest time to reach city n in the worst case. If it is impossible to reach city n in the worst case, output “-1”.

Sample Input

3
4
4
1 2 5
2 4 10
1 3 3
3 4 8
3
2
1 2 5
2 3 10
2
2
1 2 1
1 2 2

Sample Output

15
-1
2

分析与总结:

这题和
HDU 1595 find the longest of the shortest
一样。

但是有所不同，那题是没有重边的，而这题有重边，所以原来我做那题用邻接矩阵的方法不能再用了。（如果有重边的话，两点间删了一条路，还有另一条路可以用，所以不一样的）。

所以这题得用邻接表的方法来做。 用邻接表来做，其实还更简单。 和原来一样记录最短路的路径，而且还要记录这条路径是上的边。由于是用邻接表的，是用“边”来保存的，所以只需要记录下这条边在数组中的位置即可，删除的时候做个标记，对这条边不进行松弛操作即可。

代码：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;  

const int INF = 0x7fffffff;
const int VN = 1010;
const int EN = 50005;  

struct Edge{
    int v,next,w;
    bool used;
}E[EN*2];  

int n,m,size;
int head[VN];
int d[VN];
int pre[VN];
int edge[VN];
bool flag;
bool inq[VN];  

void init(){
    flag = true;
    size=0;
    memset(head, -1, sizeof(head));
    memset(pre, -1, sizeof(pre));
}
void addEdge(int u,int v,int w){
    E[size].v=v;
    E[size].w=w;
    E[size].used = true;
    E[size].next = head[u];
    head[u] = size++;
}  

void SPFA(int src){
    memset(inq, 0, sizeof(inq));
    for(int i=1; i<=n; ++i)d[i] = INF;
    d[src] = 0;
    queue<int>q;
    q.push(src);
    while(!q.empty()){
        int u = q.front();  q.pop();
        inq[u] = false;
        for(int e=head[u]; e!=-1; e=E[e].next)if(E[e].used){
            int tmp = d[u] + E[e].w;
            if(d[E[e].v] > tmp){
                d[E[e].v] = tmp;
                if(flag){
                    pre[E[e].v] = u;
                    edge[E[e].v] = e;
                }
                if(!inq[E[e].v]){
                    inq[E[e].v] = true;
                    q.push(E[e].v);
                }
            }
        }
    }
}  

int main(){
    int T,u,v,c;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=0; i<m; ++i){
            scanf("%d%d%d",&u,&v,&c);
            addEdge(u,v,c);
            addEdge(v,u,c);
        }
        SPFA(1);
        flag=false;
        if(d[n]==INF){
            puts("-1");
            continue;
        }
        int ans = -1;
        int u = n;
        while(pre[u]!=-1){
            E[edge[u]].used = false;
            SPFA(1);
            if(d[n]==INF){
                ans=-1; break;
            }
            if(d[n]>ans) ans=d[n];
            E[edge[u]].used = true;
            u = pre[u];
        }
        printf("%d\n", ans);
    }
    return 0;
}

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索and
， The
BETWEEN
harry potter、harry potter 英文版、harry potter电影、harry potter mobi、harry potter pdf，以便于您获取更多的相关知识。