HDU 2544 最短路

        链式向前星存图，Dijkstra 堆优化  HUD 2544

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 201023;
struct Node {
	int next, to, w;
} edge[SIZE];
int head[SIZE], cnt;
int dis[SIZE], sta;
bool Vis[SIZE];

void add(int form, int to, int w) {
	edge[cnt].w = w; edge[cnt].next = head[form];
	edge[cnt].to = to; head[form] = cnt++;
}

void init() {
	cnt = 0;
	memset(head, -1, sizeof head);
	memset(dis, 0x3F, sizeof dis);
	memset(Vis, false, sizeof Vis);
}

void Dijkstra() {
	priority_queue<pair<int, int> > que; que.push(make_pair(0, sta));
	while (!que.empty()) {
		int now = que.top().second; que.pop();
		if (Vis[now])
			continue;
		Vis[now] = true;
		for (int pos = head[now]; ~pos; pos = edge[pos].next)
			if (dis[edge[pos].to] > dis[now] + edge[pos].w) {
				dis[edge[pos].to] = dis[now] + edge[pos].w;
				que.push(make_pair(-dis[edge[pos].to], edge[pos].to));
			}
	}
}

int main() {
	ios::sync_with_stdio(false);
	int form, to, w, paths;

	while (cin >> sta >> paths && sta && paths) {
		init(); dis[sta] = 0;
		while (paths--) {
			cin >> form >> to >> w; 
			add(form, to, w); 
			add(to, form, w);
		}
		Dijkstra();
		cout << dis[1] << endl;
	}
}