POJ 2449 求第K短路

第一道第K短路的题目 QAQ

拿裸的DIJKSTRA + 不断扩展的A* 给2000MS过了

题意：大意是有N个station 要求从s点到t点的第k短路（不过我看题意说的好像是从t到s 可能是出题人写错了）

从这题中还真的学到了很多
1.第k短路的算法 A* 还有用边表实现dij

（注：以下部份资料来源于网上）
所谓A*就是启发是搜索说白了就是给搜索一个顺序使得搜索更加合理减少无谓的搜索. 如何来确定搜索的顺序？..也就是用一个值来表示这个值为f[n]..每次搜索取f[x]最小的拓展那么这个f[n]=h[n]+g[n]
其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n),而提高效率。

A*算法的估价函数可表示为：
f’(n) = g’(n) + h’(n)
这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值，h’(n)是n到目标的最短路经的启发值。由于这个f’(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g’(n)，但 g(n)>=g’(n) 才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h’(n)，但h(n)<=h’(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #include <iostream>

 #include <stack>

 #include <queue>

 #include <algorithm>

 #define ll long long

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 struct vertex{

     int sum, h, pos;

     bool operator < (vertex a) const{

         return a.sum + a.h < sum + h;

     }

 };

 struct sc{

        int u, v, w, next;

 }line1[MAXN*MAXN],line2[MAXN*MAXN];

 int link1[MAXN],link2[MAXN],h[MAXN],times[];

 int n, m, s, e, k;

 bool vis[MAXN];

 priority_queue <vertex> que;

 void init(){

     memset(link1, , sizeof(link1));

     memset(link2, , sizeof(link2));

     memset(vis,,sizeof(vis));

     memset(h,0x3f,sizeof(h));//h函数初始值为最大

     while (!que.empty()) que.pop();

     memset(times,,sizeof(times));

 }

 void djikstra(){

     int i,k,p;

     h[e] = ;

     for (p = ; p <= n; ++p){

         k = ;

         for (i = ; i <= n; ++i)

             if (!vis[i] && (!k||h[i]<h[k])) k = i;

         vis[k] = true;

         k = link2[k];

         while (k){

             if (h[line2[k].v] > h[line2[k].u] + line2[k].w)

                 h[line2[k].v] = h[line2[k].u] + line2[k].w;

             k = line2[k].next;

         }

     }

 }

 int Astar(){

     int t;

     vertex g,temp;

     g.pos = s;

     g.sum = ;

     g.h = h[s];

     que.push(g);

     if (s==e) ++k;

     while (!que.empty()){

         g = que.top();//每次取估价函数值最小的节点

         que.pop();

         ++times[g.pos];

         if (times[g.pos] == k && g.pos == e) return g.sum + g.h;

         if (times[g.pos] > k) continue;

         t = link1[g.pos];

         while (t){//扩展，并把其加入优先队列即openlist

             temp.sum = g.sum + line1[t].w;

             temp.h = h[line1[t].v];

             temp.pos = line1[t].v;

             que.push(temp);

             t = line1[t].next;

         }

     }

     return -;

 }

 int main(){

     int i, j;

     while(cin >> n >> m){

         init();

         for (i = ; i <= m; ++i){

             cin >> line1[i].u >> line1[i].v >> line1[i].w;

             line1[i].next = link1[line1[i].u];//记录与节点u有直接边的节点

             link1[line1[i].u] = i;

             line2[i].u = line1[i].v;

             line2[i].v = line1[i].u;

             line2[i].w = line1[i].w;

             line2[i].next = link2[line2[i].u];

             link2[line2[i].u] = i;

         }

         cin >> s >> e >> k;

         djikstra();

         cout << Astar() << endl;

     }

     return ;

 }

巴特西

POJ 2449 求第K短路

最新文章

热门文章