https://vjudge.net/problem/POJ-3259

一开始理解错题意了,以为从A->B一定得走路,B->A一定得走虫洞。emmm其实回来的时候可以路和虫洞都可以走,只要最终结果满足就好。

发现了这一点,我终于愉快地把我的floyd从wa改到了tle~

正解:用bellman-ford判断有无负圈。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int a[][], dist[];
int k, kase, n, m, w, s, e, t;
typedef struct{
int from, to;
int cost;
}Node;
Node node[];
int solve()
{
memset(dist, , sizeof(dist));//可以检查出所有的负圈
for(int i = ; i <= n; i++){
for(int j = ; j < *m+w; j++){
Node e = node[j];
if(dist[e.to] > dist[e.from]+e.cost){
dist[e.to] = dist[e.from]+e.cost;
if(i == n) return ;
}
}
}
return ;
}
int main()
{
scanf("%d", &kase);
while(kase--){
scanf("%d%d%d", &n, &m, &w);
for(int i = ; i < *m; i++){
scanf("%d%d%d", &s, &e, &t);//路是双向的
node[i].from = s; node[i].to = e;
node[i].cost = t;
i++;
node[i].from = e; node[i].to = s;
node[i].cost = t;
}
for(int i = *m; i < *m+w; i++){
scanf("%d%d%d", &s, &e, &t);//虫洞是单向的
node[i].from = s; node[i].to = e;
node[i].cost = -t;
}
if(solve()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return ;
}
04-21 13:00