hdoj1874 （優先隊列+Dijkstra），hdoj1874dijkstra

hdoj1874 （優先隊列+Dijkstra），hdoj1874dijkstra

hdoj1874

分析： 
一看題目， 就是求最短路， 這道題用的是Dijkstra+優先隊列。先說一下Dijkstra算法：每次擴展一個距離最短的節點， 更新與其相鄰點的距離。 當所有邊權都為正時， 由於不會存在一個距離更短的沒有擴展的點，所以這個點的距離不會在改變， 保證了算法的正確性。

算法步驟如下： 
G={V,E} 
1. 初始時令 S={V0},T=V-S={其余頂點}，T中頂點對應的距離值 
　　若存在〈V0,V〉，d(V0,Vi)為〈V0,Vi〉弧上的權值 
　　若不存在〈V0,Vi〉，d(V0,Vi)為∞ 
2. 從T中選取一個與S中頂點有關聯邊且權值最小的頂點W，加入到S中 
3. 對其余T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值 
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止。

偽代碼：

將所有節點狀態初始化（標記為未計算） 
設起始點s， d[s] = 0; 其他節點d[i] = MAX; 
循環n次 
{ 
　　在所有未標記的節點中， 選出d值最小的節點x； 
　　標記節點x； 
　　對於所有從x節點出發的所有邊（x， y）， 更新d[y] = min(d[y], d[x] + w(x, y))； 
}

對應代碼：

memset(v, 0, sizeof(v));
for(int i = 0; i < n; i++)
    d[i] = 10e8;
d[s] = 0;
for(int i = 1; i < n; i++)
{
    int mi = 10e8;
    for(int j = 1; j < n; j++)
    {
        if(v[j] == 0 && d[j] < mi)
            mi = d[j];
        v[j] = 1;
        for(int k = 0; k < n; k++)
            if(d[k] < d[j] + w[j][k])
                d[k] = d[j] + w[j][k];
    }
}

程序的復雜度為n方， 每一次都要求所有d中的最小值。 然而STL中的優先隊列priority_queue正好解決了這一問題。

#include<iostream> #include<cstdio> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<vector> using namespace std; int n, m, s, t, v[1005]; double d[1005]; struct edge { int v; double d; }e[1005]; struct node//存儲點的信息， 起始點到x節點的最短距離d. { int x; double d; }no[1005]; bool operator< (node a, node b) { return a.d > b.d; } vector<edge> vec[1005]; double ac(int x) { memset(v, 0, sizeof(v)); priority_queue<node> q; node tem; tem.x = s; tem.d = 0; q.push(tem);//將起始點加入隊列 while(!q.empty()) { node tem = q.top();//取出d值最小的 q.pop(); int x = tem.x; if(x == t) return tem.d; if(v[x] == 1) continue; v[x] = 1; for(int i = 0; i < vec[x].size(); i++)//更新從tem.x出發的所有邊（x,y）,d[y] = min(d[y], d[x]+w[x][y]) { int y = vec[x][i].v; if(d[y] > (tem.d + vec[x][i].d)) { d[y] = tem.d + vec[x][i].d; node node1; node1.x = y; node1.d = d[y]; q.push(node1); } } } return -1; } int main() { while(scanf("%d%d", &n, &m) != EOF) { for(int i = 0; i <= n; i++) vec[i].clear(); for(int i = 0; i <= n; i++) d[i] = 10e8; for(int i = 1; i <= m; i++) { int x, y, w; scanf("%d%d%d", &x, &y, &w); edge e; e.v = y; e.d = w; vec[x].push_back(e);//用vector存邊， e.v = x; vec[y].push_back(e); } scanf("%d%d", &s, &t); d[s] = 0; double ans = ac(s); if(ans == -1) printf("-1\n"); else printf("%.0lf\n", ans); } return 0; } View Code