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

## 两次dijkstra最短路过的，原理和网络流一样，有重边！

Posted by s221100233 at 2014-07-16 15:05:01 on Problem 2135
```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<memory.h>
using namespace std;
const int INF=1000000000;
const int N=10005;
struct Edge{int v,c,nt;};
Edge e[20*N];
int nt[N],len,n,m;
void insert(int a,int b,int c)
{
e[len].v=b;
e[len].c=c;
e[len].nt=nt[a];
nt[a]=len++;
}
int path[N],dis[N],vis[N];
struct Q{
int v,c;
friend bool operator<(Q a,Q b)
{return a.c>b.c;}
};
int dijkstra(int st,int ed)
{
for(int j=1;j<=n;j++)dis[j]=INF,vis[j]=1;
priority_queue<Q> q;
Q s;s.v=1;s.c=0;q.push(s);
path[st]=dis[st]=0;
while(!q.empty()){
Q t=q.top();q.pop();
if(!vis[t.v])continue;
vis[t.v]=0;
for(int i=nt[t.v];i;i=e[i].nt){
int u=e[i].v;
if(dis[u]>t.c+e[i].c)
{
Q in;
in.v=u;
dis[u]=in.c=t.c+e[i].c;
path[u]=t.v;
q.push(in);
}
}
}
return dis[ed];
}
void change()
{
int i,j,jj,u;
for(i=n;i>1;i=u){
u=path[i];
for(j=nt[u],jj=0;j;jj=j,j=e[j].nt)
if(e[j].v==i&&e[j].c==dis[i]-dis[u])break;
if(j==nt[u])nt[u]=e[j].nt;
else e[jj].nt=e[j].nt;
insert(i,u,-e[j].c);
}
for(i=1;i<=n;i++)
for(j=nt[i];j;j=e[j].nt)
e[j].c+=dis[i]-dis[e[j].v];
}
int main(){
int i,j,k;
while(cin>>n>>m)
{
len=1;
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c);
insert(b,a,c);
}
int ans=0;
ans+=dijkstra(1,n);
change();
ans=dijkstra(1,n)+ans*2;
printf("%d\n",ans);
}
return 0;
}
```

Followed by: