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;
}