大逃离（洛谷 P2829）

大逃离

题目背景

zrz走进了一个奇葩的迷宫，他发现自己迷路了，想逃出来，他好不容易数完了所有的路，累的快晕了，只好叫你帮忙咯。

题目描述

这是一棵有n个节点的图，有m条双向边，每一条路有w个单位距离，zrz在1的位置，出口在n的位置，不过zrz脑子出了点bug，于是不想走最短的路，想走第2短的路，第2短路径允许与最短路径有重边，然后也可以重复通过一些节点和路，注意如果有多条路径都是最短路径，那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个（起点和终点除外），那么他就不敢进去。

输入格式

第一行3个数：n,m,k

接下来m行：每行3个数，u，v，w。表示从u到v有一条权值为w的边。（u,v<=n，w<=10000）

输出格式

一个数：表示从s走到t的第2短路的值，如果不存在，输出-1

输入 #1

4 4 1

1 2 100

2 4 200

2 3 250

3 4 100

输出 #1

450

输入 #2

4 4 3

1 2 100

2 4 200

2 3 250

3 4 100

输出 #2

500

次短路的板子题，这道题比较坑的是，会有重边；这里的重边要加入图中，但是算一个顶点连接的点时，要把重边排除；

举个例子：加入1–2，然后又加入2—1，这时1到2就有4条边，因为加一条边要双向；但是1的连接点就只有1个，2的连接点也只是一个；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
using namespace std;
int n,m,k;
int head[5010],cnt;
struct Nod{
	int to,next,x;
	int w;
}edge[200100];
void add(int p,int q,double w){
	edge[cnt].x=p;
	edge[cnt].to=q;
	edge[cnt].w=w;
	edge[cnt].next=head[p];
	head[p]=cnt++;
}
int dis1[5010],dis2[5010];
bool vis[5010];
int sum[5010];
struct di{
	double fi;
	int se;//fi边权
	bool operator < (const di &a)const {
		return fi > a.fi;         // 从小到大  ，fi小的优先级别高
	}
};
void dijkstra(int s,int dis[]){//开始点，存储长度的数组 
	memset(vis,false,sizeof(vis));
	priority_queue<di>qu;
	dis[s]=0;
	di n1;n1.se=s;n1.fi=0;
	qu.push(n1);
	while(!qu.empty()){
		di n2=qu.top();
		qu.pop();
		if(vis[n2.se]) continue;
		vis[n2.se]=true;
		for(int i=head[n2.se];~i;i=edge[i].next){
			int u=edge[i].to;
			if(dis[u]>dis[n2.se]+edge[i].w&&(sum[u]>=k||u==n||u==1)){
				dis[u]=dis[n2.se]+edge[i].w;
				di n3;n3.fi=dis[u];n3.se=u;
				qu.push(n3);
			}
		} 
	}
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		dis1[i]=dis2[i]=2e9;
	}
	int p,q,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&p,&q,&w);
		if(p==q) continue;
		add(p,q,w);
		add(q,p,w);
	}
	int v[5010];
	for(int i=1;i<=n;i++){
		memset(v,0,sizeof(v));
		for(int j=head[i];~j;j=edge[j].next) 
		if(!v[edge[j].to]){//判重
			sum[i]++;	
			v[edge[j].to]=1;
		}
	}
	//for(int i=1;i<=n;i++) cout<<i<<" "<<s[i]<<endl;
	dijkstra(1,dis1);
	dijkstra(n,dis2);
	int ans=2e9;//初始化答案 
    int minn=dis1[n];//最短路 
    for(int i=0;i<cnt;i++){
        if(dis1[edge[i].x]+edge[i].w+dis2[edge[i].to]>minn)
            ans=min(dis1[edge[i].x]+edge[i].w+dis2[edge[i].to],ans);//更新   
        if(dis1[edge[i].to]+edge[i].w+dis2[edge[i].x]>minn)
            ans=min(dis1[edge[i].to]+edge[i].w+dis2[edge[i].x],ans);
    }
    if(ans==2e9) printf("-1\n");
    else printf("%d\n",ans);
	return 0;
}