心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
正向图反向图各求一次单源最短路。
以下是我的代码:
#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 阅读(216) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理