首页 > 代码库 > POJ 3268 最短路应用
POJ 3268 最短路应用
POJ3268
题意很简单 正向图跑一遍SPFA 反向图再跑一边SPFA 找最大值即可。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<queue> #include<vector> using namespace std; const int maxn=1000+1,maxm=100000+1,INF=1e+8; int len[maxn][maxn],len1[maxn][maxn],dist[maxn],dist1[maxn]; vector<int> path[maxn],path1[maxn]; int n,m,source; void SPFA(int dist[],int d[][maxn],vector<int>son[],int source) { bool inq[maxn]; int times[maxn]; memset(inq,0,sizeof(inq)); memset(times,0,sizeof(times)); for(int i=1;i<=n;i++) dist[i]=INF; dist[source]=0; queue<int>q; q.push(source); times[source]++; inq[source]=true; while(!q.empty()) { int now=q.front(); q.pop(); inq[now]=false; for(int i=0;i<son[now].size();i++) { int np=son[now][i]; if(dist[np]>dist[now]+d[now][np]) { dist[np]=dist[now]+d[now][np]; if(times[np]>n)return; if(!inq[np]){times[np]++;q.push(np);} } } } } int main() {freopen("t.txt","r",stdin); scanf("%d%d%d",&n,&m,&source); for(int i=0;i<m;i++) { int a,b,l; scanf("%d%d%d",&a,&b,&l); path[a].push_back(b);len[a][b]=l; path1[b].push_back(a);len1[b][a]=l; } SPFA(dist,len,path,source); SPFA(dist1,len1,path1,source); int ans=0; for(int i=1;i<=n;i++) { if((dist[i]+dist1[i])>ans)ans=dist[i]+dist1[i]; } printf("%d\n",ans); return 0; }
POJ 3268 最短路应用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。