阅读量:0
1.题目
题目链接：7-4 猛犸不上 Ban - 2021 RoboCom 世界机器人开发者大赛-本科组（决赛） (pintia.cn)
2.题解
//题意：s->s和s->t最短 //1.s->t直接使用模板dijkstra //2.s->s最短：分解成s->i+i->s //求第一段s->i就是模板dijkstra //因为不能重复，求i->s之前需要将s->i经过的路线全部标记一下，表示不可达 //然后再使用模板dijkstra即可 #include<bits/stdc++.h> using namespace std; const int N=510; const int inf=0x3f3f3f3f; //规定无穷大 int n,m,s,t; int g[N][N]; //存储图 bool ok[N][N],vis[N]; //是否路线被标记不可达，dijkstra的vis访问数组 int dis[N],pre[N]; //距离数组、前驱数组 void dijkstra(int st){ memset(dis,inf,sizeof(dis)); memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); dis[st]=0; for(int k=1;k<=n;k++){ //1.选择dis距离最小的坐标 int tmp=-1; for(int i=1;i<=n;i++){ if(!vis[i]&&(tmp==-1||dis[tmp]>dis[i])) tmp=i; } if(tmp==-1) break; vis[tmp]=true; //2.更新数组 for(int i=1;i<=n;i++){ if(ok[tmp][i]) continue; //ok标记之后，相当于tmp与i不可达 if(dis[i]>dis[tmp]+g[tmp][i]){ dis[i]=dis[tmp]+g[tmp][i]; pre[i]=tmp; } } } } //求st->ed的路径(可达)+结合dijktra(st)才能正确使用 //是为了在求s->中的i->s路径之前需要将s->i的路线全部标记 vector<int> p; //存储路线 void getPath(int st,int ed){ p.clear(); int x=ed; while(x!=st){ p.push_back(x); x=pre[x]; } p.push_back(st); reverse(p.begin(),p.end()); } int main(void){ cin>>n>>m>>s>>t; memset(g,inf,sizeof(g)); for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; g[a][b]=g[b][a]=c; } //1. 求s->t dijkstra(s); int res2=dis[t]; if(res2==inf) res2=-1; //2. 求s->s int res1=inf; for(int i=1;i<=n;i++){ //i为中转点，但是不能是s //1-1. s->i if(i==s) continue; memset(ok,0,sizeof(ok)); dijkstra(s); if(dis[i]==inf) continue; //第一段不可达，不可能是中转点 int d1=dis[i]; //记录第一段的值 //将s->i经过路径标记为不可达 getPath(s,i); for(int j=0;j<p.size()-1;j++){ ok[p[j]][p[j+1]]=ok[p[j+1]][p[j]]=1; } //1-2. 求i->s dijkstra(i); if(dis[s]==inf) continue; //第二段不可达 res1=min(res1,d1+dis[s]); } if(res1==inf) res1=-1; cout<<res1<<" "<<res2<<endl; if(res1==-1) cout<<"Lose!"; else if(res2==-1) cout<<"Win!"; else if(res1<res2) cout<<"Win!"; else cout<<"Lose!"; return 0; } 