P1186 玛丽卡
2018-06-17 22:20:14来源:未知 阅读 ()
题目描述
麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。
因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。
在这个国家中每两个城市之间最多只有一条路相通,并且我们知道从一个城市到另一个城市路上所需花费的时间。
麦克在车中无意中听到有一条路正在维修,并且那儿正堵车,但没听清楚到底是哪一条路。无论哪一条路正在维修,从玛丽卡所在的城市都能到达麦克所在的城市。
玛丽卡将只从不堵车的路上通过,并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间,这样他就能保证他的女朋友离开该城市足够远。
编写程序,帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入输出格式
输入格式:
第一行有两个用空格隔开的数N和M,分别表示城市的数量以及城市间道路的数量。1≤N≤1000,1≤M≤N*(N-1)/2。城市用数字1至N标识,麦克在城市1中,玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A,B和V。其中1≤A,B≤N,1≤V≤1000。这些数字表示在A和城市B中间有一条双行道,并且在V分钟内是就能通过。
输出格式:
输出文件的第一行中写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处。
输入输出样例
5 7 1 2 8 1 4 10 2 3 9 2 4 10 2 5 1 3 4 7 3 5 10
27
先跑一边最短路,然后记下最短路上的点,删除之后再跑最短路
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 const int MAXN=1000001; 9 const int maxn=0x7ffff; 10 void read(int &n) 11 { 12 char c='+';int x=0;bool flag=0; 13 while(c<'0'||c>'9') 14 {c=getchar();if(c=='-')flag=1;} 15 while(c>='0'&&c<='9') 16 {x=x*10+(c-48);c=getchar();} 17 flag==1?n=-x:n=x; 18 } 19 struct node 20 { 21 int u,v,w,nxt; 22 }edge[MAXN]; 23 int head[MAXN]; 24 int num=1; 25 int n,m; 26 int vis[1001]; 27 int dis[1001]; 28 int pre[1001]; 29 int flag=0; 30 void add_edge(int x,int y,int z) 31 { 32 edge[num].u=x; 33 edge[num].v=y; 34 edge[num].w=z; 35 edge[num].nxt=head[x]; 36 head[x]=num++; 37 } 38 int ans=0; 39 int can[1001][1001]; 40 void SPFA() 41 { 42 memset(vis,0,sizeof(vis)); 43 for(int i=1;i<=n;i++) 44 dis[i]=maxn; 45 queue<int>q; 46 q.push(1); 47 dis[1]=0; 48 vis[1]=1; 49 while(q.size()!=0) 50 { 51 int p=q.front(); 52 q.pop(); 53 vis[p]=0; 54 for(int i=head[p];i!=-1;i=edge[i].nxt) 55 { 56 int will=edge[i].v; 57 if(dis[will]>dis[p]+edge[i].w&&can[edge[i].u][edge[i].v]==0) 58 { 59 if(flag==0) 60 pre[will]=p; 61 dis[will]=dis[p]+edge[i].w; 62 if(!vis[will]) 63 { 64 q.push(will); 65 vis[will]=1; 66 } 67 } 68 } 69 } 70 ans=max(ans,dis[n]); 71 } 72 int main() 73 { 74 read(n);read(m); 75 pre[1]=-1; 76 for(int i=1;i<=n;i++) 77 head[i]=-1; 78 for(int i=1;i<=m;i++) 79 { 80 int x,y,z; 81 read(x);read(y);read(z); 82 add_edge(x,y,z); 83 add_edge(y,x,z); 84 } 85 SPFA(); 86 flag=1; 87 int now=n; 88 while(pre[now]!=-1) 89 { 90 can[now][pre[now]]=1; 91 can[pre[now]][now]=1; 92 SPFA(); 93 can[now][pre[now]]=0; 94 can[pre[now]][now]=0; 95 now=pre[now]; 96 } 97 printf("%d",ans); 98 return 0; 99 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1041 传染病控制
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash