本文主要是介绍poj 3259 Wormholes 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：虫洞问题，现在有n个点，m条边，代表现在可以走的通路，比如从a到b和从b到a需要花费c时间，现在在地上出现了w个虫洞，虫洞的意义就是你从a到b话费的时间是-c(时间倒流,并且虫洞是单向的)，现在问你从某个点开始走，能回到从前
解题思路：其实给出了坐标，这个时候就可以构成一张图，然后将回到从前理解为是否会出现负权环，用bellman-ford就可以解出了 Wormholes
Description
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
Input
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2.. M+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: a bidirectional path between S and E that requires Tseconds to traverse. Two fields might be connected by more than one path.
Lines M+2.. M+ W+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output
Sample Input
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8
Sample Output
NO YES#include<stdio.h> #include<string.h> int count,dis[10000]; int INF=100000000; int n,m,w; struct node {int u,v,w; } q[60005]; void eduge(int cu,int cv,int cw) {q[count].u=cu;q[count].v=cv;q[count].w=cw;count++; } int BULLFOUND() {int i,j;for(i=1; i<=n; i++)dis[i]=INF;dis[1]=0;for(i=1; i<n; i++)for(j=0; j<count; j++)if(dis[q[j].v]>dis[q[j].u]+q[j].w)dis[q[j].v]=dis[q[j].u]+q[j].w;for(j=0; j<count; j++)if(dis[q[j].v]>dis[q[j].u]+q[j].w)return 0;return 1;} int main() {int f,s,e,t,p;scanf("%d",&f);while(f--){count=0;scanf("%d %d %d",&n,&m,&w);while(m--){scanf("%d %d %d",&s,&e,&t);eduge(s,e,t);eduge(e,s,t);}while(w--){scanf("%d %d %d",&s,&e,&t);eduge(s,e,-t);}p=BULLFOUND();if(p==0)printf("YES\n");elseprintf("NO\n");}return 0;}
这篇关于poj 3259 Wormholes 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
