全网有哪些网站可以做淘客,温州微网站制作哪里有,客户管理软件免费版,郑州做网站建设的公司桐人的约会
题目大意#xff1a;
删掉一条边#xff0c;让一个图中的最短路最长
原题#xff1a;
题目描述
这是一个风和日丽的日子#xff0c;桐人和诗乃在约会。他们所在的城市共有N个街区#xff0c;和M条道路#xff0c;每条道路连接两个不同的街区#xff0c;…桐人的约会
题目大意
删掉一条边让一个图中的最短路最长
原题
题目描述
这是一个风和日丽的日子桐人和诗乃在约会。他们所在的城市共有N个街区和M条道路每条道路连接两个不同的街区并且通过一条道路需要花费一些时间。他们现在处于N号街区正在享受幸福时光的桐人完全忘记了他的手机被亚丝娜安装了监控装置的事情此时亚丝娜已经得知了桐人的位置以及他正在和一个妹子约会的事实十分愤怒于是从她所在的1号街区火速赶往N号街区。现在这个城市中有一条道路正在维修不能通行不过不论是哪条道路处于维修中均存在一条路径可以从1号街区前往N号街区而且亚丝娜一定会选取最短路前往N号街区。现在你很好奇桐人的美好时光最多还能持续多久即亚丝娜最多要花费多长的时间才能到达N号街区。
输入
第1行两个正整数NMN表示街区个数M表示道路数。 第2到M1行 每行三个整数 u,v,w 表示存在一条连接u和v的道路通过这条道路花费的时间为w 数据保证没有重边和自环
输出
一个整数表示最多花费的时间。
输入样例
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10输出样例
27说明
【数据规模】
30% N5, M10 60% N1000,M10000,w1 100% N1000, MN*(N-1)/2,1w1000
解题思路
先找到最短路然后将最短路中的每一段路依次删掉每删掉一次跑一遍SPFA
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,w,h,x,y,c,ans,p[1005],b[1005],la[1005],las[1005],head[1005];
struct rec
{int l,to,next,pd;
}a[2000005];
void SPFA(int now)
{a[now].pd1;//去掉memset(b,127/3,sizeof(b));queueintd;//SPFAd.push(1);p[1]1;b[1]0;while(!d.empty()){hd.front();d.pop();for (int ihead[h];i;ia[i].next)if (b[h]a[i].lb[a[i].to](!a[i].pd)){b[a[i].to]b[h]a[i].l;if (!p[a[i].to]){p[a[i].to]1;d.push(a[i].to);}}p[h]0;}a[now].pd0;//返回ansmax(ans,b[n]);//取最大值
}
void spfa()//SPFA
{memset(b,127/3,sizeof(b));queueintd;d.push(1);p[1]1;b[1]0;while(!d.empty()){hd.front();d.pop();for (int ihead[h];i;ia[i].next)if (b[h]a[i].lb[a[i].to]){b[a[i].to]b[h]a[i].l;las[a[i].to]h;//前缀la[a[i].to]i;//相连接的线if (!p[a[i].to]){p[a[i].to]1;d.push(a[i].to);}}p[h]0;}for (int in;i1;ilas[i])SPFA(la[i]);//删掉这条线路再跑最短路
}
int main()
{scanf(%d %d,n,m);for (int i1;im;i){scanf(%d %d %d,x,y,c);a[w].toy;//存储a[w].lc;a[w].nexthead[x];head[x]w;a[w].tox;a[w].lc;a[w].nexthead[y];head[y]w;}spfa();//最短路printf(%d,ans);
}
