RT
P2349 金字塔
dijkstra16分

#include<bits/stdc++.h>
using namespace std;
int N, M, u, v, w, dis[1100], dq[1100],vv, qz[1010][1010], zdz[1100],minx=1000000000;
bool pd[1010];
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d%d", &u, &v, &w);
		qz[u][v] = w;
		qz[w][v] = w;
	}
	pd[1] = 1;
	zdz[1] = 0;
	dis[1] = 0;
	for (int i = 2; i <= N; i++) {
		dis[i] = 1e7;
		if (qz[1][i] != 0) {
			dis[i] = qz[1][i] * 2;
			zdz[i] = qz[1][i];
			dq[i] = 1;
		}
	}
//	for (int i = 1; i <= N; i++) {
//		cout << pd[i] << " " << dis[i] << " " << dq[i] <<" "<<zdz[i]<< endl;
//	}
	for(int i=2;i<=N;i++){
		minx=99999999;
		for(int j=1;j<=N;j++){
			if(!pd[j]){
				if(dis[j]<minx){
					vv=j;
					minx=dis[j];
				}
			}
		}
		pd[vv]=1;
		for(int j=1;j<=N;j++){
			if(!pd[j]&&qz[vv][j]!=0){
				if(qz[vv][j]>zdz[vv]){
					if(dis[j]>dis[vv]-zdz[vv]+qz[vv][j]+qz[vv][j]){
						dis[j]=dis[vv]-zdz[vv]+qz[vv][j]+qz[vv][j];
						zdz[j]=qz[vv][j];
						dq[j]=vv;
					}
				}else{
					if(dis[j]>dis[vv]+qz[vv][j]){
						dis[j]=dis[vv]+qz[vv][j];
						zdz[j]=zdz[vv];
						dq[j]=vv;
					}
				}
			}
		}
	}
	cout<<dis[N];
	return 0;
}

不会排版，各位神犇凑合着看