# Poj Solution 2135

```http://poj.org/problem?id=2135

#include<iostream>
#include"stdio.h"
#include"vector"
using namespace std;
struct edge
{
int from;
int to;
int len;
int opp;
};

vector<edge> e[1010];
int from[1010],dis[1010],n,m;
bool sign[1010];
edge *along[1010];

void dijstra()
{
int i,j,k,to;
for(i=0;i<n;i++)
{
sign[i]=0;
dis[i]=999999999;
}

sign[0]=0;
from[0]=-1;
dis[0]=0;

for(;;)
{
k=-1;
for(j=0;j<n;j++)
if(!sign[j]&&(k<0||dis[j]<dis[k]))
k=j;
if(k<0)break;

sign[k]=1;

for(j=0;j<e[k].size();j++)
if(dis[to=e[k][j].to]>dis[k]+e[k][j].len)
{
dis[to]=dis[k]+e[k][j].len;
from[to]=k;
sign[to]=0;
along[to]=&e[k][j];
}
}
}

void init()
{
int i,a,b,c;
edge eg;
scanf("%d %d",&n,&m);

for(i=0;i<n;i++)
e[i].clear();

for(i=0;i<m;i++)
{
scanf("%d %d %d",&a,&b,&c);
a--,b--;
eg.len=c;

eg.to=b;eg.from=a;
e[a].push_back(eg);

eg.to=a;eg.from=b;
e[b].push_back(eg);

e[a][e[a].size()-1].opp=e[b].size()-1;
e[b][e[b].size()-1].opp=e[a].size()-1;
}
}

int ans;
void doit()
{
int i;
dijstra();
ans=dis[n-1];

i=n-1;
while(from[i]>=0)
{
e[i][along[i]->opp].len*=-1;
along[i]->len=99999999;
i=from[i];
}
dijstra();
ans+=dis[n-1];
}

int main()
{
init();
doit();
printf("%dn",ans);
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.