为啥用spfa过了,dijs没过
查看原帖
为啥用spfa过了,dijs没过
1271310
mysb楼主2024/10/23 08:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,s,m,qq,a1,b1,ans,mx,k;
const long long INF=0x3f3f3f3f;
vector<pair<long long,long long> > g[10000000];
bool vis[10000000];
long long di[10000000];
map<string,long long> ss;
void dijs(long long x){
	for(long long i=1;i<=n;i++){
		di[i]=INF;
		vis[i]=0;
	}
	priority_queue<pair<int,int> > q;
	di[x]=0;
	q.push({0,x});
	while(!q.empty()){
		long long u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto i:g[u]){
		long long w=i.second;
		long long v=i.first;
			if(di[v]>di[u]+w&&!vis[v]){
				di[v]=di[u]+w;
//				if(di[v]==0)di[v]=w;
				q.push({-di[v],v});
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		string a,b;
		cin>>a>>b>>w;
//		g[v].push_back({u,w});
	if(ss.count(a)==0){
		k++;
		ss[a]=k;
	}
	if(ss.count(b)==0){
		k++;
		ss[b]=k;
	}
	g[ss[a]].push_back({ss[b],w});
	}
	long long q;
	cin>>q;
	while(q--){
		string a,b;
		cin>>a>>b;
		dijs(ss[a]);
		if(di[ss[b]]!=INF)cout<<di[ss[b]]<<"\n";
		else cout<<"Roger\n";
	}
	
	return 0;
} 
2024/10/23 08:59
加载中...