链接:https://ac.nowcoder.com/acm/contest/26077/1038
来源:牛客网
题目描述
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。John的每个农场有M条小路(无向边)连接着N(从1到N标号)块地,并有W个虫洞。
现在John想借助这些虫洞来回到过去(在出发时刻之前回到出发点),请你告诉他能办到吗。John将向你提供F个农场的地图。没有小路会耗费你超过10410^4104秒的时间,当然也没有虫洞回帮你回到超过10410^4104秒以前。
输入描述:
第一行一个整数F,表示农场个数;
对于每个农场:
第一行,三个整数N,M,W;
接下来M行,每行三个数S,E,T,表示在标号为S的地与标号为E的地中间有一条用时T秒的小路;
接下来W行,每行三个数S,E,T,表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。
输出描述:
输出共F行,如果John能在第i个农场实现他的目标,就在第i行输出YES,否则输出NO。
示例1
输入
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
输出
NO YES
备注:
对于全部数据,1≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤1041 /le F /le 5,1 /le N /le 500,1 /le M /le 2500,1 /le W /le 200,1 /le S,E /le N,|T| /le10^41≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤104。
分析
1.如果存在负环,则这条负环至少经过n 个点。这样是o(n)
2.如果记录每个点入队次数就要o(n^2)
3.由于可能负环不在根节点位置,所以要预先把所有点放进队列里。
ps:不要忘记初始化
//-------------------------代码---------------------------- //#define int ll const int N = 1e6+10; int n,m,w; V<pii> e[N]; int dist[N]; bool vis[N]; int cnt[N]; bool spfa(int st) { ms(dist,0x3f);ms(vis,0); queue<int> q; fo(i,1,n) { dist[i] = 0; vis[i] = 1; q.push(i); cnt[i] = 0; } while(q.size()) { auto t = q.front();q.pop(); vis[t] = 0; for(auto it:e[t]) { int ver = it.first,W = it.second; if(dist[ver] > dist[t] + W) { dist[ver] = dist[t] + W; cnt[ver] = cnt[t] + 1; if(cnt[ver] >= n) return 1; if(!vis[ver])q.push(ver),vis[ver] = 1; } } } return 0; } void solve() { cin>>n>>m>>w; fo(i,1,n) e[i].clear(); fo(i,1,m) { int a,b,c;cin>>a>>b>>c; e[a].pb({b,c}),e[b].pb({a,c}); } fo(i,1,w) { int a,b,c;cin>>a>>b>>c; e[a].pb({b,-c}); } if(spfa(1)) { YES; } else { NO; } } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/281926.html