Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个代码 差分约束系统+dijkstra#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator