评分详情

提交的代码：

#include<cstdio>
using namespace std;
const long long INF=0x7fffffffffffffff;//极大值 


struct call_que{//队列 
	private://头、尾指针与队列本体 
		int head,tail,q[2503];
	public:
	void in(int a){//入队。这是阉割版，不考虑溢出 
		if(++tail>2502) tail=1;
		q[tail]=a;
	}
	int out(){//成功返回边号，失败返回 0。
		if(head==tail) return 0;
		if(++head>2502) head=1;
		return q[head];
	}
}que;//大概我是疯了才自己写这玩意儿。。。
//一个更简便的方式：queue头 


int cnt,h[2503];//cnt为点数，h装每个点的最后一个出度
struct call_edge{//链式前向星 
	int st,ed,w,lst;//起点、终点、权以及一个指向上一个同起点边的指针
}edge[400003];
void cun(int x,int y,int w){//存储操作 
	edge[++cnt].lst=h[x],  h[x]=cnt;//指向上一个同起点边，更新链表头指针 
	edge[cnt].st=x, edge[cnt].ed=y, edge[cnt].w=w;//边存入 
}
	
	
int main(){
	int n,m,x,y,z;
	long long p[2503];//存起点到每一点的当前最短距离 
	scanf("%d%d",&n,&m);
	
	p[1]=0;//记 起点到起点 最短距离为0 
	for(int i=2;i<=n;++i) p[i]=INF;//其它初始化为极大值
	 
	for(int i=1;i<=m;++i){//输入边、存边 
		scanf("%d%d%d",&x,&y,&z);
		cun(x,y,z);
		cun(y,x,z);
	}
	
	que.in(1);//起点入队 
	while(x=que.out())//此时x是队首泵出元素。若队空，结束 
		for(int i=h[x];i>0;i=edge[i].lst ){//对此点查询每个链上的边 
			if (p[ edge[i].st ] == INF) continue;
			if (p[ edge[i].ed ] > p[ edge[i].st ]+ edge[i].w)//若成功松弛 
				p[ edge[i].ed ] = p[ edge[i].st ]+ edge[i].w,
				que.in(edge[i].ed);//则被更新点入队 
		}
	printf("%lld",p[n]);//输出 
	return 0;
}

贝尔曼-福特的队列优化。队列是自己写的。测试了一下好像没有问题？