2 条题解
-
0
正解：Dijkstra算法
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e5+10; vector< PII > G[N]; int dis[N],vis[N]; void dij(int st) { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis));dis[st]=0; priority_queue< PII , vector< PII > , greater< PII > >q; q.push({0,st}); while(q.size()) { int x=q.top().second;q.pop(); if(vis[x])continue; vis[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(dis[y]>dis[x]+w) { dis[y]=dis[x]+w; q.push({dis[y],y}); } } } } int main() { int n,m,st,a,b;scanf("%d%d%d%d%d",&m,&n,&st,&a,&b); for(int i=1,x,y,w;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); G[x].push_back(make_pair(y,w)); G[y].push_back(make_pair(x,w)); } dij(st); int s1=min(dis[a],dis[ b ]); dij(a); int s2=dis[ b ]; printf("%d\n", s1+s2 ); return 0; }SPFA+Deque优化解法
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e5+10; vector< PII > G[N]; int dis[N],vis[N]; void spfa(int st) { memset(vis,0,sizeof(vis)); vis[st]=true; memset(dis,0x7f,sizeof(dis));dis[st]=0; deque< int >q; q.push_front(st); while(q.size()) { int x=q.front();q.pop_front(); vis[x]=false; for(auto i:G[x]) { int y=i.first,w=i.second; if(dis[y]>dis[x]+w) { dis[y]=dis[x]+w; if(!vis[y]) { vis[y]=true; if(q.size() && dis[y]<dis[q.front()]) q.push_front(y); else q.push_back(y); } } } } } int main() { int n,m,st,a,b;scanf("%d%d%d%d%d",&m,&n,&st,&a,&b); for(int i=1,x,y,w;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); G[x].push_back(make_pair(y,w)); G[y].push_back(make_pair(x,w)); } spfa(st); int s1=min(dis[a],dis[b]); spfa(a); int s2=dis[b]; printf("%d\n", s1+s2 ); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:57:51
正解dijkstral，54ms：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e5+10; vector< PII > G[N]; int dis[N],vis[N]; void dij(int st) { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis));dis[st]=0; priority_queue< PII , vector< PII > , greater< PII > >q; q.push({0,st}); while(q.size()) { int x=q.top().second;q.pop(); if(vis[x])continue; vis[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(dis[y]>dis[x]+w) { dis[y]=dis[x]+w; q.push({dis[y],y}); } } } } int main() { int n,m,st,a,b;scanf("%d%d%d%d%d",&m,&n,&st,&a,&b); for(int i=1,x,y,w;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); G[x].push_back(make_pair(y,w)); G[y].push_back(make_pair(x,w)); } dij(st); int s1=min(dis[a],dis[ b ]); dij(a); int s2=dis[ b ]; printf("%d\n", s1+s2 ); return 0; }
spfa+deque优化：#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e5+10; vector< PII > G[N]; int dis[N],vis[N]; void spfa(int st) { memset(vis,0,sizeof(vis)); vis[st]=1; memset(dis,0x7f,sizeof(dis));dis[st]=0; deque< int >q; q.push_front(st); while(q.size()) { int x=q.front();q.pop_front(); vis[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(dis[y]>dis[x]+w) { dis[y]=dis[x]+w; if(!vis[y]) { vis[y]=1; if(q.size() && dis[y]<dis[q.front()]) q.push_front(y); else q.push_back(y); } } } } }int main() { int n,m,st,a,b;scanf("%d%d%d%d%d",&m,&n,&st,&a,&b); for(int i=1,x,y,w;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); G[x].push_back(make_pair(y,w)); G[y].push_back(make_pair(x,w)); } spfa(st); int s1=min(dis[a],dis[b]); spfa(a); int s2=dis[b]; printf("%d\n", s1+s2 ); return 0; }
</p>
- 1
