题目电波 3259 Wormholes
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stdio.h> using namespace std; #define maxn 100010 #define inf 0x3f3f3f3f struct ac{ int to,va; ac(){} ac(int a,int b){ to=a,va=b; } }; vector<ac>q[maxn]; int dis[maxn],vis[maxn]; bool fa[maxn]; int n,m,s; void init(){ ;j<=maxn;j++) q[j].clear(); } bool spfa(){ memset(vis,,sizeof(vis)); memset(fa,,sizeof(fa)); memset(dis,inf,sizeof(dis)); dis[]=; queue<int>pq; pq.push(); while(!pq.empty()){ int u=pq.front(); pq.pop(); fa[u]=; ;j<q[u].size();j++){ int v=q[u][j].to; int va=q[u][j].va; if(dis[v]>dis[u]+va){ dis[v]=dis[u]+va; if(!fa[v]){ fa[v]=; vis[v]++; pq.push(v); if(vis[v]>=n){ ; } } } } } ; } int main(){ int t; cin>>t; while(t--){ init(); cin>>n>>m>>s; ;j<m;j++){ int u,v,va; scanf("%d%d%d",&u,&v,&va); q[u].push_back(ac(v,va)); q[v].push_back(ac(u,va)); } ;j<s;j++){ int u,v,va; scanf("%d%d%d",&u,&v,&va); q[u].push_back(ac(v,-va)); } if(spfa()){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } }