最短路——玛丽卡

原文链接：https://www.luogu.com.cn/problem/P1186

AC代码：

#include<iostream>
#include<string.h> 
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
int mapp[1005][1005],ans=0;
int visit[1005][1005],set[1005],pre[1005];
int n,m,inf=1e9;
int lowc0[1005],lowc1[1005];
typedef struct node{
	int id,w;
	bool operator <(const node &a)const{
		return a.w<w;
	}
}node;
node nod,nodd;
priority_queue<node> que;
void deal(){
	int i,j;
	for(i=0;i<1005;i++){
		lowc0[i]=inf;lowc1[i]=inf;pre[i]=i;
	}
	nod.id=n;nod.w=0;lowc0[n]=0;lowc1[n]=0;
	que.push(nod);
	while(que.size()!=0){
		nod=que.top();que.pop();//
		if(set[nod.id]==1) continue;
		set[nod.id]=1;
		if(nod.id==1) break ;
		for(i=1;i<=n;i++){
			if(set[i]==1) continue;
			if(mapp[nod.id][i]==0) continue;
			if(lowc0[nod.id]+mapp[nod.id][i]<lowc0[i]){
				lowc0[i]=lowc0[nod.id]+mapp[nod.id][i];
				pre[i]=nod.id;
				if(set[i]==0){
					nodd.id=i;nodd.w=lowc0[i];
					que.push(nodd);
				}
			}
		}
	}
	j=1;
	while(pre[j]!=j){
		i=pre[j];//cout<<i<<" "<<j<<endl;
		visit[i][j]=1;
		visit[j][i]=1;
		j=i;
	}
}
void deal0(){
	int i,j;
	for(i=0;i<1005;i++){
		lowc1[i]=inf;
	}
	nod.id=n;nod.w=0;lowc1[n]=0;
	que.push(nod);
	while(que.size()!=0){
		nod=que.top();que.pop();//cout<<nod.id<<endl;
		if(set[nod.id]==1) continue;
		set[nod.id]=1;
		if(nod.id==1) break ;
		for(i=1;i<=n;i++){
			if(set[i]==1||visit[nod.id][i]==1) continue;
			if(mapp[nod.id][i]==0) continue;
			if(lowc1[nod.id]+mapp[nod.id][i]<lowc1[i]){
				lowc1[i]=lowc1[nod.id]+mapp[nod.id][i];
				if(set[i]==0){
					nodd.id=i;nodd.w=lowc1[i];
					que.push(nodd);
				}
			}
		}
	}
	ans=max(ans,lowc1[1]);
}
int main(){
	int i,j;
	memset(mapp,0,sizeof(mapp));
	memset(visit,0,sizeof(visit));
	memset(set,0,sizeof(set));
	cin>>n>>m;
	for(i=0;i<m;i++){
		int p,q,r;
		cin>>p>>q>>r;
		mapp[p][q]=r;
		mapp[q][p]=r;
	}
	deal();
	j=1;
	while(pre[j]!=j){
		memset(visit,0,sizeof(visit));
		memset(set,0,sizeof(set));
		i=pre[j];
		visit[i][j]=1;visit[j][i]=1;
		deal0();
		j=i;
		while(!que.empty()){
		    que.pop();
	    }
	}
	cout<<ans<<endl;
	return 0;
}