心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
构造反向图,分别求单源最短路,然后求和即可。
以下是我的代码:
#include<iostream>
#include
<queue>
#include
<cstdio>
#include
<cstring>
using namespace std;
const int kMaxn(1000007);
const int kMaxm(1000007);
const long long kInf(0x7f7f7f7f7f7f7f7f);
struct Edge
{
    
int v,w;
};

void SPFA(int n,int first[kMaxn],int next[kMaxm],Edge e[kMaxm],long long d[kMaxn])
{
    queue
<int> q;
    
bool inq[kMaxn];
    memset(inq,
false,sizeof(inq));
    
for(int i=1;i<=n;i++)
        d[i]
=kInf;
    d[
1]=0;
    q.push(
1);
    inq[
1]=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(d[v]>d[u]+w)
            {
                d[v]
=d[u]+w;
                
if(!inq[v])
                {
                    q.push(v);
                    inq[v]
=true;
                }
            }
        }
    }
}

int n,m;
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];
int cnt2,first2[kMaxn],next2[kMaxm];Edge e2[kMaxm];
long long d[kMaxn],d2[kMaxn];

int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    {
        cnt
=cnt2=0;
        memset(first,
-1,sizeof(first));
        memset(first2,
-1,sizeof(first2));

        scanf(
"%d%d",&n,&m);
        
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;

            cnt2
++;
            e2[cnt2].v
=u;e2[cnt2].w=w;
            next2[cnt2]
=first2[v];
            first2[v]
=cnt2;
        }

        SPFA(n,first,next,e,d);
        SPFA(n,first2,next2,e2,d2);

        
long long ans(0);
        
for(int i=1;i<=n;i++)
            ans
+=d[i]+d2[i];

        cout
<<ans<<endl;
    }

    
return 0;
}
posted on 2011-07-31 09:34 lee1r 阅读(198) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

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