网站在线建设,企点账户中心,企业网站建设与管理简述,网站建设高职考题目所谓次短路#xff0c;就是又次又短的路 #xff08;逃#xff09;
解析
使用两遍swap是更新sec的好方法 一定要判断是严格次短才更新sec的答案#xff01;
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int … 所谓次短路就是又次又短的路 逃
解析
使用两遍swap是更新sec的好方法 一定要判断是严格次短才更新sec的答案
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N200050;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,k;
struct node{int to,nxt,w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],w};fi[x]cnt;
}
int du[N];
int mn[N],sec[N];
#define pr pairint,int
#define mkp make_pair
priority_queuepr,vectorpr,greaterpr q;
int num[N];
void dij(){memset(mn,0x7f,sizeof(mn));memset(sec,0x7f,sizeof(sec));mn[1]0;q.push(mkp(0,1));while(!q.empty()){int nowq.top().second,wq.top().first;q.pop();if(wsec[now]) continue;num[now];//printf(now%d w%d\n,now,w);for(int ifi[now];~i;ip[i].nxt){int top[i].to;if(to!1to!ndu[to]k) continue;int wwwp[i].w,flag0;int qwqww;//printf( to%d ww%d mn%d sec%d\n,to,ww,mn[to],sec[to]);if(wwmn[to]){swap(ww,mn[to]);flag1;}if(ww!mn[to]wwsec[to]) swap(ww,sec[to]),flag1;if(flag) q.push(mkp(qwq,to));//printf( to%d ww%d mn%d sec%d\n,to,ww,mn[to],sec[to]);}}return;
}
bool vis[5050][5050];
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();kread();for(int i1;im;i){int xread(),yread(),wread();if(!vis[x][y]x!y){du[x];du[y];vis[x][y]vis[y][x]1;}addline(x,y,w);addline(y,x,w);}dij();printf(%d\n,sec[n]1e9?sec[n]:-1);return 0;
}
/*14 3 1 22 7 5 03 4 -10 19 10 1 0
*/
