2341949_ac_280ms_5144k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;

int ans[6000][2],t[6000];
int li[100000][3],deg[6000],*e[6000],*c[6000],n,m;

struct dat{
	int p,dis;
	bool operator <(const dat &b) const { return dis > b.dis;}
}tmp;

priority_queue<dat> q;
int main(){
	int i,p,d;
	for(scanf("%d%d",&n,&m),memset(deg,0,sizeof(deg)),i=0;i<m;
		scanf("%d%d%d",&li[i][0],&li[i][1],&li[i][2]),
		li[i][0]--,li[i][1]--,deg[li[i][0]]++,deg[li[i][1]]++,i++);
	for(i=0;i<n;e[i]=new(int[deg[i]]),c[i]=new(int[deg[i]]),deg[i]=0,i++);
	for(i=0;i<m;
		e[li[i][0]][deg[li[i][0]]]=li[i][1],
		c[li[i][0]][deg[li[i][0]]]=li[i][2],deg[li[i][0]]++,
		e[li[i][1]][deg[li[i][1]]]=li[i][0],
		c[li[i][1]][deg[li[i][1]]]=li[i][2],deg[li[i][1]]++,i++);
memset(t,0,sizeof(t));
tmp.p = tmp.dis = 0;
q.push( tmp);
	for(;!q.empty();q.pop())
	{
		p=q.top().p;	d=q.top().dis;
		if(t[p]<2){
			ans[p][t[p]]=d;	t[p]++;
			for(i=0;i<deg[p];i++)	
				if(t[e[p][i]]<2)
				{
				tmp.dis = d+c[p][i];tmp.p = e[p][i];
				q.push(tmp);
			}
		}
	}
	printf("%d\n",ans[n-1][1]);
	return 1;
}