P2829 大逃离
2019-08-19
题目背景
zrz走进了一个奇葩的迷宫,他发现自己迷路了,想逃出来,他好不容易数完了所有的路,累的快晕了,只好叫你帮忙咯。
题目描述
这是一棵有n个节点的图,有m条双向边,每一条路有w个单位距离,zrz在1的位置,出口在n的位置,不过zrz脑子出了点bug,于是不想走最短的路,想走第2短的路,第2短路径允许与最短路径有重边,然后也可以重复通过一些节点和路,注意如果有多条路径都是最短路径,那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个(起点和终点除外),那么他就不敢进去。
Solve
1.次短路问题+SPFA。
2.设起点为s,终点t。
3.设dis1[i]为s到节点i的最短路,dis2[i]为t到节点2的最短路。
4.设次短路ans。
5.ans即为min{dis1[u]+w+dis2[v]}(u,v,w表示每条边的两侧端点和权值),ans!=dis1[t]。
Tip
1.蒟蒻的我并不会证明该过程的正确性。
2.直接连接的地方小于k个,此处指的是点数。
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 400010
using namespace std; //标准开头
int n,m,k; //同题
int e,r,dist; //输入时的端点,权值
int ans=1e9; //答案
int du[N]; //直接连接的点数
int dis1[N],dis2[N]; //同Solve
int first[N],next[N],len; //邻接表,len表示边数
bool vis[N];
int f[5001][5001]; //f[i][j]>0,表示i与j直接相连
struct note{ //邻接表
int u,v,w;
}d[N];
void add(int e,int r,int dist){ //邻接表
d[++len].u=e;
d[len].v=r;
d[len].w=dist;
next[len]=first[e];
first[e]=len;
}
void spfa(int s,int *dis){ //标准SPFA
memset(vis,false,sizeof(vis));
dis[s]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int e=q.front();
q.pop();
vis[e]=false;
for(int i=first[e];i!=-1;i=next[i]){
if(du[d[i].v]<k&&d[i].v!=1&&d[i].v!=n) continue; //排除度数小于k
if(dis[d[i].v]>dis[e]+d[i].w){
dis[d[i].v]=dis[e]+d[i].w;
if(!vis[d[i].v]){
vis[d[i].v]=true;
q.push(d[i].v);
}
}
}
}
}
int main()
{
memset(first,-1,sizeof(first));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) dis1[i]=dis2[i]=1e9;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e,&r,&dist);
f[e][r]++;
f[r][e]++;
add(e,r,dist);
add(r,e,dist);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) if(f[i][j]) du[i]++;
}
spfa(1,dis1);
spfa(n,dis2);
for(int i=1;i<=len;i++){
if(dis1[d[i].u]+d[i].w+dis2[d[i].v]!=dis1[n]&&ans>dis1[d[i].u]+d[i].w+dis2[d[i].v]) ans=dis1[d[i].u]+d[i].w+dis2[d[i].v];
}
if(ans==1e9) printf("-1");
else printf("%d",ans);
return 0;
}