原來(lái)用stl的優(yōu)先隊(duì)列這么爽，比賽時(shí)候多用，heap太容易打錯(cuò)了，畢竟沒(méi)ghost_wei那么bt(heap,就幾行,都打爛了-_-)
pku3159:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1 << 28;
const int MAXN = 30010;
struct PQNode 
{
int u, key;
//pq默認(rèn)用<判斷優(yōu)先級(jí),key大優(yōu)先,若要key小優(yōu)先,則加上!或<改成>即可
friend bool operator<(const PQNode &a, const PQNode &b) { return !(a.key < b.key); }
};
int n, m;
vector<int> adjv[MAXN], adjw[MAXN];
int dijkstraPQ(int st, int en) {
int i, v, w, dist[MAXN], chk[MAXN];
priority_queue<PQNode> pq;
PQNode tmp, cp;
memset(chk, 0, sizeof(chk));
for (i=0; i<n; i++) dist[i] = INF;
dist[st] = 0;
tmp.u = st; tmp.key = 0;
pq.push(tmp);
while (!pq.empty()) {
cp = pq.top();
pq.pop();
if (cp.u == en) return dist[en];
if (chk[cp.u]) continue;
chk[cp.u] = 1;
for (i=0; i<adjv[cp.u].size(); i++) {
v = adjv[cp.u][i]; w = adjw[cp.u][i];
if (!chk[v] && (dist[v]==INF || dist[v]>cp.key+w)) {
dist[v] = cp.key+w;
tmp.u = v; tmp.key = dist[v];
pq.push(tmp);
}
}
}
return -1;
}
int main() {
int i, j, k, u, v, w;
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i=0; i<m; i++) {
scanf("%d%d%d", &u, &v, &w);
u--; v--;
adjv[u].push_back(v);
adjw[u].push_back(w);
}
printf("%d\n", dijkstraPQ(0, n-1));
return 0;
}
posted on 2007-11-03 16:40
豪 閱讀(1351)
評(píng)論(4) 編輯 收藏 引用 所屬分類:
算法&ACM