2021 RoboCom 世界机器人开发者大赛-本科组（决赛）7-4 猛犸不上 Ban_2021 robocom 世界机器人开发者大赛-本科组(决赛)7-5超时

输入样例:

5 6 1 5
1 2 1
2 3 2
3 4 3
4 1 5
3 5 4
4 5 1

输出样例:

在这里给出相应的输出。例如：

11 6
Lose!

解题思路：对于第二种情况直接以s为起点跑一遍最短路即可，这里主要说一下第一种情况，因为dijkstra是不能跑有环的情况的，所以我们要转变一下，我们可以枚举每一个于s点直接相连的边，与s点直接相连的点为p,那么我们只要能得到从s点到p点的最短路（这个过程中不能经过我们当前这条与s直接相连的边）加上s到p点的距离就是s到s自身的一个回路的长度，这样我们对于所有直接相连的边进行枚举，取一个最小值即可。

上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510;
const int M=1e5+10;
int n,m,s,t;
int dist[N],g[N][N];
bool vis[N];
void dijkstra(int s,int u,int v)
{
	memset(dist,0x3f3f3f3f,sizeof dist);
	memset(vis,false,sizeof vis);
	dist[s]=0;
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		if(!vis[j]&&(t==-1||dist[t]>dist[j]))
		t=j;
		vis[t]=true;
		for(int j=1;j<=n;j++)
		{
			if(t==u&&j==v)
			continue;
			if(dist[j]>dist[t]+g[t][j])
			{
				dist[j]=dist[t]+g[t][j];
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s>>t;
	memset(g,0x3f3f3f3f,sizeof g);
	for(int i=1;i<=m;i++)
	{
		int u,v,val;
		cin>>u>>v>>val;
		g[u][v]=g[v][u]=min(g[u][v],val);
	}
	int ans1=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		if(i==s||g[i][s]==0x3f3f3f3f)
		continue;
		dijkstra(s,s,i);
		ans1=min(ans1,dist[i]+g[i][s]);
	}
	
	dijkstra(s,0,0);
	if(ans1!=0x3f3f3f3f)
	cout<<ans1<<" ";
	else
	cout<<"-1 ";
	if(dist[t]!=0x3f3f3f3f)
	cout<<dist[t]<<endl;
	else
	cout<<"-1"<<endl;
	if(ans1<dist[t])
	cout<<"Win!"<<endl;		
	else
	cout<<"Lose!"<<endl;
	return 0;
}