Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个代码 差分约束系统+dijkstra

Posted by chenshenglizuibang at 2011-11-02 19:27:16 on Problem 3159
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>


using namespace std;

const int MAXn=30010,MAXed=150010,INF=1000000000;

int first[MAXn],next[MAXed],u[MAXed],v[MAXed],w[MAXed],dis[MAXn],edg,n,m;
typedef pair<int,int>pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void add(int pu,int pv,int pw)
{
    u[edg]=pu;
    v[edg]=pv;
    w[edg]=pw;
    next[edg]=first[pu];
    first[pu]=edg;
    edg++;
}

int dijkstra()
{
    
    int vis[MAXn];
    
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        dis[i]=INF;
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        pii u=q.top();
        q.pop();
        int x=u.second;
        if(vis[x])continue;
        vis[x]=1;
        for(int e=first[x];e!=-1;e=next[e])
        {
            if(dis[v[e]]>dis[x]+w[e])
            {
                dis[v[e]]=dis[x]+w[e];
                q.push(make_pair(dis[v[e]],v[e]));
            }
        }
    }
     return dis[n];
     
}

int main(int argc, char *argv[])
{
    
    edg=0;
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    printf("%d\n",dijkstra());
    //system("PAUSE");
    return EXIT_SUCCESS;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator