正向图反向图各求一次单源最短路。
以下是我的代码：
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(1007);
const int kMaxm(100007);
const long long kInf(0x7f7f7f7f7f7f7f7fll);
struct Edge
{
int v,w;
};
int n,m,x;
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];
int first2[kMaxn],next2[kMaxm];Edge e2[kMaxm];
long long d1[kMaxn],d2[kMaxn];
void SPFA(int first[kMaxn],int next[kMaxn],Edge e[kMaxm],int start,long long dist[kMaxn])
{
queue<int> q;
bool inq[kMaxn]={false};
for(int i=1;i<=n;i++)
dist[i]=(i==start?0:kInf);
q.push(start);
inq[start]=true;
while(!q.empty())
{
int u(q.front());q.pop();
inq[u]=false;
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v),w(e[i].w);
if(dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
if(!inq[v])
{
q.push(v);
inq[v]=true;
}
}
}
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&x)==3)
{
cnt=0;
memset(first,-1,sizeof(first));
memset(first2,-1,sizeof(first));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
cnt++;
e[cnt].v=v;e[cnt].w=w;
next[cnt]=first[u];
first[u]=cnt;
e2[cnt].v=u;e2[cnt].w=w;
next2[cnt]=first2[v];
first2[v]=cnt;
}
SPFA(first,next,e,x,d1);
SPFA(first2,next2,e2,x,d2);
long long ans(0);
for(int i=1;i<=n;i++)
ans=max(ans,d1[i]+d2[i]);
cout<<ans<<endl;
}
return 0;
}
posted on 2011-07-31 09:52
lee1r 阅读(203)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论