HDoj 1874(優先キュー+Dijkstra)
タイトルリンク分析:タイトルを見ると、最短ルートを求めます.この問題はDijkstra+優先キューを使用しています.まずDijkstraアルゴリズムについてお話しします.最も距離の短いノードを拡張するたびに、隣接する点との距離を更新します.すべてのエッジ重みが正の場合,より短い距離の拡張されていない点は存在しないため,この点の距離は変化せず,アルゴリズムの正確性を保証した.
アルゴリズムの手順は以下の通りである:G={V,E}1.初期時令S={V 0},T=V-S={残りの頂点},Tにおける頂点に対応する距離値に〈V 0,V〉が存在する場合,d(V 0,Vi)は〈V 0,Vi〉弧上の重み値に〈V 0,Vi〉が存在しない場合,d(V 0,Vi)は∞2となる.TからSの頂点に関連付けるエッジがあり、重み値が最も小さい頂点Wを選択し、Sに加える.残りのTの頂点の距離値を変更する:Wを中間頂点として加え、V 0からViまでの距離値を短くすると、Sにすべての頂点、すなわちW=Viが含まれるまで、この距離値を変更するには、上記の手順2、3を繰り返します.
疑似コード:
すべてのノード状態を初期化(未計算とマーク)して開始点s,d[s]=0を設定します.その他のノードd[i]=MAX;ループn回{すべてのタグ付けされていないノードの中で、d値が最も小さいノードxを選択する;タグノードx;すべてのxノードから出発するすべてのエッジ(x,y)に対して、d[y]=min(d[y],d[x]+w(x,y))を更新する;
対応コード:
プログラムの複雑さはn方であり,毎回すべてのdの最小値が要求される.しかしSTLの優先キューpriority_queueはちょうどこの問題を解決した.
アルゴリズムの手順は以下の通りである:G={V,E}1.初期時令S={V 0},T=V-S={残りの頂点},Tにおける頂点に対応する距離値に〈V 0,V〉が存在する場合,d(V 0,Vi)は〈V 0,Vi〉弧上の重み値に〈V 0,Vi〉が存在しない場合,d(V 0,Vi)は∞2となる.TからSの頂点に関連付けるエッジがあり、重み値が最も小さい頂点Wを選択し、Sに加える.残りのTの頂点の距離値を変更する:Wを中間頂点として加え、V 0からViまでの距離値を短くすると、Sにすべての頂点、すなわちW=Viが含まれるまで、この距離値を変更するには、上記の手順2、3を繰り返します.
疑似コード:
すべてのノード状態を初期化(未計算とマーク)して開始点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
");
else
printf("%.0lf
", ans);
}
return 0;
}