最短路模板,加一个判断一下最后一步dis[n]与inf关系,若大于等于,那就输出qwb baka就成。
#include <bits/stdc++.h> using namespace std; int n,m; const int maxn=200005; const int inf=0x3f3f3f3f; struct node { int v; int w; node(int v,int w):v(v),w(w){} bool operator<(const node & t)const { return w>t.w; } }; vector<node>dij[maxn]; int vis[maxn]; int dis[maxn]; void dijkstra(int s) { memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); dis[s]=0; priority_queue<node> Q; Q.push(node(s,dis[s])); while(!Q.empty()) { int u=Q.top().v; //点 Q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=0;i<dij[u].size();i++) { int v=dij[u][i].v; int w=dij[u][i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; Q.push(node(v,dis[v])); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; dij[u].push_back(node(v,w)); dij[v].push_back(node(u,w)); } dijkstra(1); if(dis[n]>=inf) printf("qwb baka\n"); else cout<<dis[n]<<endl; return 0; }
另外一个基本一样的,为了熟悉模板qaq
#include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int inf=0x3f3f3f3f; const int maxn=200005; struct node { int to; //终点 int s; //权值 }; vector<node> f[maxn]; int dis[maxn]; int vis[maxn]; int n,m; void dijkstra(int t) { memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pii,vector<pii>,greater<pii> > q; dis[t]=0; q.push(pii(0,t)); while(!q.empty()) { pii x=q.top(); q.pop(); int tt=x.second; if(vis[tt]) { continue; } vis[tt]=1; for(int i=0;i<f[tt].size();i++) { node a=f[tt][i]; if(dis[a.to]>dis[tt]+a.s) { dis[a.to]=dis[tt]+a.s; q.push(pii(dis[a.to],a.to)); } } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; f[u].push_back({v,w}); f[v].push_back({u,w}); } dijkstra(1); if(dis[n]>=inf) { cout<<"qwb baka"<<endl; } else { cout<<dis[n]<<endl; } return 0; }