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 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 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;js 		dijkstra(i); 		if(dis[s]==inf) continue;  //第二段不可达 		res1=min(res1,d1+dis[s]);  	} 	if(res1==inf) res1=-1; 	cout<