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->tdijkstra(s);int res2=dis[t];if(res2==inf) res2=-1;//2. 求s->sint 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->sdijkstra(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;
} 
