HDU 1595 find the longest of the shortest
The of HDU Find Longest Shortest
2023-09-11 14:21:01 时间
在最短的时间最长。
含义非常模糊标题,做4小时度过理解问题……对中国不会死!
!。
它说,从 N 至 1 可能有一些办法的道路被封锁,不能。乞讨N 至 1 在最短的时间最长。
一般想法就是枚举 每条路不能通过时候的最短路。时间花费太高。
m*O(SPFA)。
能够先做一次SPFA。把最短路径记录下来。
其它的路无论是不是 封堵了,最短路都是这么多。
然后再 枚举 ,把最短路径上的路依次删掉,求最短。
最多 (n-1)*O(SPFA);
最后输出最长的。
(我的代码太长,事实上能够把两个SPFA写在一起,推断一下就好,算了,关电脑睡觉。累!
)
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; struct lx { int v,len; }; vector<lx>g[1001]; int n,m,ans; int path[1001]; struct edge { int u,v; }; stack<edge>flag; void spfa() { queue<int>q; bool vis[1001]; int dis[1001]; for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0; q.push(n); dis[n]=0,vis[n]=1; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j<g[u].size();j++) { int v=g[u][j].v; int len=g[u][j].len; if(dis[v]>dis[u]+len) { dis[v]=dis[u]+len; path[v]=u; if(!vis[v]) { vis[v]=1; q.push(v); } } } } ans=dis[1]; int tmp=1; while(tmp!=0) { edge now; now.v=tmp; tmp=path[tmp]; now.u=tmp; if(tmp!=0) flag.push(now); } } void SPFA(edge now) { queue<int>q; bool vis[1001]; int dis[1001]; for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0; q.push(n); dis[n]=0,vis[n]=1; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j<g[u].size();j++) { int v=g[u][j].v; int len=g[u][j].len; if(u==now.u&&v==now.v)continue; if(dis[v]>dis[u]+len) { dis[v]=dis[u]+len; path[v]=u; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(dis[1]!=INF) ans=max(ans,dis[1]); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { int u,v,len; for(int i=1;i<=n;i++) g[i].clear(); while(m--) { scanf("%d%d%d",&u,&v,&len); lx now; now.len=len; now.v=v,g[u].push_back(now); now.v=u,g[v].push_back(now); } while(!flag.empty())flag.pop(); spfa(); while(!flag.empty()) { edge now=flag.top();flag.pop(); //printf("%d -> %d\n",now.u,now.v); SPFA(now); } printf("%d\n",ans); } }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
相关文章
- Twitter OA prepare: Visit element of the array
- Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
- What the Hell Happened This Week? - Week of 12/5/2021 The Daily Show with Trevor Noah
- The implementation of iterators in C# and its consequences (part 1) Raymond Chen
- What are the benefits to using anonymous functions instead of named functions for callbacks and parameters in JavaScript event code?
- golang错误:The process cannot access the file because it is being used by another process
- Google Earth Engine(GEE)——The bands of the specified image contains different projections
- The Use of Aliases in ElasticSearch
- .NET错误The 'targetFramework' attribute in the <compilation> element of the Web.config file is used only to target version 4.0 and later of the .NET Framework
- Can't connect to X11 window server using ':1.0' as the value of the DISPLAY variable.
- 华为游戏登录验签失败can not find publicKey of the cp
- HDU 5542 The Battle of Chibi (离散化+树状数组优化DP)
- HDU 4461 The Power of Xiangqi (水题)
- 继承“HibernateDaoSupport”后,报“The hierarchy of the type AccoutDaoImpl is inconsistent”的解决方案
- The resource identified by this request is only capable of generating responses with characteristics
- The Impact of Disks on RocksDB State Backend in Flink: A Case Study
- 【 Gym - 101138K 】 The World of Trains (DP)
- HDU 3215 The first place of 2^n (数论-水题)
- Having the Result Set of a Stored Proc Sent to You by RSS Feed.
- BEA-150021 - The admin server failed to authenticate the identity of the user username starting the managed server.
- 万卷书 - 成为领导的方法 The Making of a Leader
- * resolve_conffiles: Existing conffile /etc/config/dhcp is different from the conffile in the new package. The new conffile will be placed at /etc/config/dhcp-opkg.