• POJ3259虫洞题解


    题目

    链接

    http://poj.org/problem?id=3259

    字面描述

    Wormholes
    Time Limit: 2000MS Memory Limit: 65536K
    Total Submissions: 92250 Accepted: 33922
    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: A single integer, F. F farm descriptions follow.
    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 T seconds 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

    Lines 1…F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
    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
    Hint

    For farm 1, FJ cannot travel back in time.
    For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.
    Source

    USACO 2006 December Gold

    思路

    这道题是靠虫洞无限减少时间,我们可以用SPFA去判断负环,也可以用Floyd去判断负环。

    代码实现

    #include
    #include
    #include
    using namespace std;
    
    const int maxn=500+10;
    int f,n,m,w;
    int g[maxn][maxn];
    inline bool Floyd(){
    	for(int k=1;k<=n;k++){
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				if(g[i][j]>g[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];
    			}
    			if(g[i][i]<0)return true;
    		}
    	}
    	return false;
    }
    int main(){
    	scanf("%d",&f);
    	while(f--){
    		memset(g,0x3f,sizeof(g));
    		scanf("%d%d%d",&n,&m,&w);
    		for(int i=1;i<=m;i++){
    			int u,v,w;
    			scanf("%d%d%d",&u,&v,&w);
    			if(g[u][v]>w||g[v][u]>w)g[u][v]=g[v][u]=w;
    		}
    		for(int i=1;i<=w;i++){
    			int u,v,w;
    			scanf("%d%d%d",&u,&v,&w);
    			g[u][v]=-w;
    		}
    		if(!Floyd())printf("NO\n");
    		else printf("YES\n"); 
    	}
    	return 0;
    } 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
  • 相关阅读:
    GBASE生态 | 您有一份8月份的GBase数据库适配报告等待查收
    【面试题精讲】Mysql如何实现乐观锁
    口袋参谋:如何快速下载直通车图,这个方法你用过吗?
    求臻医学张怡然博士,肿瘤基因检测“解码之旅”的践行者
    stm32以中断方式扫描矩阵键盘
    餐厅订座预约小程序的效果如何
    室内设计常用的涂料清单
    华为软件开发实习生笔试2021.3.31(三)
    如何优化网站SEO(百度SEO优化的6个方案及密度)
    【数据结构C/C++】优先(级)队列
  • 原文地址:https://blog.csdn.net/weixin_42178241/article/details/126012543