2135.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 106 行

#include"iostream.h"
#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("%d\n",ans);
	return 0;
}