Remmarguts' Date | Time Limit: 4000MS | | Memory Limit: 65536K | | Total Submissions: 12450 | | Accepted: 3422 |
Description "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate. Input The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000). Output A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead. Sample Input 2 2
1 2 5
2 1 4
1 2 2
Sample Output 14 Source |
第K短路問題，大概意思就是給你N個點，M條邊，邊是有向的，給你每條邊的邊權，給你一個S起始點，T結束點，和一個K，求S到T的第K短路。
SPFA+A*啟發(fā)式搜索。
說說啟發(fā)式搜索吧：
通常在解決問題的時候，我們需要用到搜索算法，由已知狀態(tài)推出新的狀態(tài)，然后檢驗新的狀態(tài)是不是就是我們要求的最優(yōu)解。檢驗完所有的狀態(tài)實際上就相當于遍歷了一張隱式圖。遺憾的是，所有的狀態(tài)組成的狀態(tài)空間往往是成指數(shù)級別增長的，也就造成了遍歷需要用到指數(shù)級別的時間，因此，純粹的暴力搜索，時空效率都比較低。當然，我們在生活中遇到了類似于搜索的問題，我們并不會盲目地去搜尋每一種狀態(tài)，我們會通過我們的思維，選擇一條最接近于目標的路徑或者是近似于最短的路徑去完成搜索任務。當我們想要計算機去完成這樣一項搜索任務的時候，就得讓計算機像人一樣能夠區(qū)分盡量短的路徑，以便高效地找到最優(yōu)解。這時可以把計算機看作是一種智能體(agent)可以實現(xiàn)由初始狀態(tài)向目標狀態(tài)的轉(zhuǎn)移。
有一種貪心策略，即每一步轉(zhuǎn)移都由計算機選擇當前的最優(yōu)解生成新的狀態(tài)，一直到達目標狀態(tài)為止。這樣做的時間效率雖然較高，但是貪心的策略只是用到了局部的最優(yōu)解，并不能保證最后到達目標狀態(tài)得到的是全局最優(yōu)解。在能保證全局最優(yōu)解的范圍內(nèi)，貪心算法還是很有用的。比如說我們熟知的Dijkstra算法求單源最短路。每次選擇距離源節(jié)點最短距離的待擴展節(jié)點進行擴展，最后就能生成源節(jié)點到所有節(jié)點的最短路徑。下面會講到Dijkstra的擴展，當理解了這個算法之后，我想，你會對Dijkstra有更深入的理解。
這就是A*算法。定義初始狀態(tài)S，目標狀態(tài)t，g(s)是由初始狀態(tài)轉(zhuǎn)移到當前狀態(tài)s所經(jīng)過的路徑長度，h*(s)是當前狀態(tài)s距離目標狀態(tài)t的實際長度，但是一般情況下我們是不知道h*(s)的值的，所以還要定義一個估價函數(shù)h(s)，是對h*(s)函數(shù)值的下界的估計，也就是有h(s)<=h*(s)，這樣需要一個條件，使得由s1生成的每狀態(tài)s2，都有h(s1)<=h(s2)，這是一個相容的估價函數(shù)。再定義f(s)=g(s)+h(s)為啟發(fā)函數(shù)，因為h(s)是單調(diào)遞增的，所以f(s)也是單調(diào)遞增的。這樣f(s)就估計出了由初始狀態(tài)的總體代價。A*算法就通過構造這樣一個啟發(fā)函數(shù)，將所有的待擴展狀態(tài)加入到隊列里，每次從隊列里選擇f(s)值最小的狀態(tài)進行擴展。由于啟發(fā)函數(shù)的作用，使得計算機在進行狀態(tài)轉(zhuǎn)移的時候盡量避開了不可能產(chǎn)生最優(yōu)解的分支，而選擇相對較接近最優(yōu)解的路徑進行搜索，提高了搜索效率。
講到這里，可能已經(jīng)對A*算法的概念有點眉目了。下面我再來做一個比較，就用上面講到的Dijkstra的例子。Dijkstra算法說的是每次選擇距離源點最短距離的點進行擴展。當然可以看做事先將源點到所有節(jié)點距離的值保存在一個優(yōu)先隊列里，每次從優(yōu)先隊列里出隊最短距離的點擴展，每個點的擴展涉及到要更新隊列里所有待擴展節(jié)點的距離值，每個節(jié)點只能進隊一次，就需要有一個表來記錄每個節(jié)點的入隊次數(shù)（就是算法中用到的標記數(shù)組）。將Dijkstra求最短路的方法擴展，這道題目要求的是兩點間第k短路。類比于Dijkstra算法可以首先確定下面幾個搜索策略：
1、用優(yōu)先隊列保存節(jié)點進行搜索。
2、放開每個節(jié)點的入隊次數(shù)，求k短路，每個節(jié)點可以入隊k次。
首先看第一個策略，在A*算法中用優(yōu)先隊列就是要用到啟發(fā)函數(shù)f(s)確定狀態(tài)在優(yōu)先隊列里面的優(yōu)先級。其實Dijkstra用到的優(yōu)先隊列實際上就是估價函數(shù)值為0，啟發(fā)函數(shù)f(s)=g(s)，即是選取到源點距離最近的點進行擴展。因為h(s)=0滿足了估價函數(shù)相容這個條件。這題求k短路就不能單純的使用h(s)=0這個估價函數(shù)。解決這道題的時候選取h(x)=dt(x), dt(x)是x節(jié)點到目標節(jié)點的最短距離。最短距離可以開始由Dijkstra直接求得。
再看第二個策略，控制每個節(jié)點的入隊（或出隊）次數(shù)為k次，可以找到第k短路徑。可能這樣想有點主觀的套用，那么我就先來證明這樣一個結論：
如果x是s到t的第k短路徑上的一個節(jié)點，那么由這條路徑s到x是s到x的第m短路徑，則不可能有m>k。用反證法很容易得出：如果這條路徑是s到x的第m短路徑，如果m>k，那么經(jīng)過x到t的路徑就有m-1條比當前路徑要短，不符合當前路徑是s到t的第k短路徑。
代碼：
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAXN 10005 //邊數(shù)
#define inf 1 << 25
using namespace std;
int dis[MAXN];
struct node
{
int v, dis;
};
struct edge
{
int v, w;
friend bool operator < (edge a, edge b)
{
return (a.w + dis[a.v]) > (b.w + dis[b.v]);
}
};
vector <node> map[MAXN];
vector <node> remap[MAXN];
int n, m; //n是節(jié)點數(shù)，m是邊數(shù)。
int s, t, k; //s是起始點，t是結束點，k是第k小。
void init()
{
int i;
for (i = 0; i < MAXN; ++i)
map[i].clear();
for (i = 0; i < MAXN; ++i)
remap[i].clear();
}
void spfa(int s)
{
int i;
bool used[MAXN];
memset(used, 0, sizeof(used));
for (i = 0; i < MAXN; ++i)
dis[i] = inf;
dis[s] = 0;
used[s] = true;
queue <int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
used[u] = false;
for (i = 0; i < remap[u].size(); ++i)
{
node p = remap[u][i];
if (dis[p.v] > dis[u] + p.dis)
{
dis[p.v] = dis[u] + p.dis;
if (!used[p.v])
{
used[p.v] = true;
q.push(p.v);
}
}
}
}
}
int a_star()
{
if (s == t)
k++; //注意，起始和結束一樣，k要+1；
if (dis[s] == inf)
return -1;
int i, x, len, cnt[MAXN];
edge n1, n2;
priority_queue <edge> q;
memset(cnt, 0, sizeof(cnt));
n1.v = s;
n1.w = 0;
q.push(n1);
while (!q.empty())
{
n2 = q.top();
q.pop();
x = n2.v;
len = n2.w;
cnt[x]++;
if (cnt[t] == k)
return len;
if (cnt[x] > k)
continue;
for (i = 0; i < map[n2.v].size(); ++i)
{
n1.v = map[n2.v][i].v;
n1.w = len + map[n2.v][i].dis;
q.push(n1);
}
}
return -1;
}
int main()
{
int i;
node p;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
int a, b, l;
for (i = 1; i <= m; ++i)
{
scanf("%d%d%d", &a, &b, &l);
p.v = b;
p.dis = l;
map[a].push_back(p);
p.v = a;
remap[b].push_back(p);
}
scanf("%d%d%d", &s, &t, &k);
spfa(t);
int ans = a_star();
printf("%d\n", ans);
}
return 0;
}
posted on 2011-10-17 15:19
LLawliet 閱讀(693)
評論(0) 編輯 收藏 引用 所屬分類:
圖論