本文正體字版由OpenCC轉換
這是一個K短路徑問題，解決方法有Yen算法等等。但是這並不是一個一般的K短路徑問題，這是一個有向無環圖。所以可以考慮動態規劃(記憶化搜索)的思想解決。
記頂點i到目標點N的k短路徑的長度爲Dis[i,k]。可以知道每個頂點Dis[i,*]，都是由大於i的頂點j，Dis[j,*]推得的。由於源點和目標都是確定的，我們可以從目標節點倒推回源點。
建立原圖的逆向圖，即從1開始到N。記從頂點1到i的當前路徑的長度爲S，訪問頂點i鄰接的頂點j，令新的到j的路徑長度F爲S+ (i,j)。把F加入到Dis[j]中，並只保留前K小的。然後訪問頂點j。如果F大於所有Dis[j]，則不能用該路徑鬆弛頂點j，不訪問j。當全部訪問完以後，按照要求輸出Dis[N]即可。
對於維護Dis[i]，可以使用堆、甚至平衡樹等高級數據結構。但是考慮到K並不是很大，維護一個數組即可。當插入新的元素V時，如果已有的數目不足K，直接插入；如果已經爲K，在這K個元素中找到最大值Max，如果V<Max，用V替換Max；如果V>=Max，不必插入。
時間複雜度爲O(M*K)
/*
ID: cmykrgb1
PROG: cowjog
LANG: C++
*/
#include <iostream>
#define MAX 1001
#define MAXK 101
#define INF 0x7fffffff
using namespace std;
class list
{
public:
list *next;
int p,v;
list(int tp,int tv)
{
p=tp;
v=tv;
next=0;
}
};
class tadjl
{
public:
list *first,*last;
tadjl()
{
first=last=0;
}
void ins(int p,int v)
{
if (first)
last=last->next=new list(p,v);
else
first=last=new list(p,v);
}
};
class monotony
{
public:
int Size,cnt;
int C[MAXK];
monotony(int K)
{
Size=K;
cnt=0;
}
bool ins(int v)
{
int i,j,max=0;
if (cnt<Size)
{
C[cnt++]=v;
}
else
{
for (i=0;i<cnt;i++)
{
if (C[i]>max)
{
max=C[i];
j=i;
}
}
if (v>=max)
return false;
C[j]=v;
}
return true;
}
};
int N,M,K;
tadjl adjl[MAX];
monotony *Dis[MAX];
void init()
{
int i,a,b,v;
freopen("cowjog.in","r",stdin);
freopen("cowjog.out","w",stdout);
cin >> N >> M >> K;
for (i=1;i<=M;i++)
{
cin >> a >> b >> v;
adjl[b].ins(a,v);
}
for (i=1;i<=N;i++)
{
Dis[i]=new monotony(K);
}
for (i=0;i<K;i++)
{
Dis[N]->C[i]=INF;
}
}
void dfs(int i,int S)
{
int j,v,F;
bool succ;
list *k;
for (k=adjl[i].first;k;k=k->next)
{
j=k->p;
v=k->v;
F=v+S;
succ=Dis[j]->ins(F);
if (succ && j!=N)
{
dfs(j,F);
}
}
}
inline int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
void print()
{
int i;
qsort(Dis[N]->C,K,sizeof(Dis[N]->C[0]),cmp);
for (i=0;i<K;i++)
{
if (Dis[N]->C[i]!=INF)
cout << Dis[N]->C[i];
else
cout << -1;
cout << endl;
}
}
int main()
{
init();
dfs(1,0);
print();
return 0;
}
官方題解
參考翻譯
翻譯By BYVoid
我們正在考慮的一個無環圖，我們希望找到的K ≤ 100最短路徑。由於圖是環自然有序的頂點，動態規劃是一個很好的第一種辦法。
假設我們知道頂點i到穀倉頂點N的K短路徑，我們可以用來計算從頂點i - 1到N的K短路徑。我們認爲所有從頂點的i - 1 的出邊。假設頂點的i - 1有d個出邊，這d個出邊的末端頂點都大於的i - 1，我們可以從每個這些頂點計算K短路徑。
考慮將要計算的頂點的i - 1至所有這些d * K條路徑，頂點i - 1到N的K短路徑頂將來自與這些d * K條路徑。我們可以通過合併這些d列表中項目，有效地維護一個列表，存儲從i-1到N的K短路徑。在每一個頂點需要d * K的時間。計算所有的頂點爲O(MK)時間。既然M = 10000和K = 100，這將是約1000000個操作。
原文
We are given an acyclic graph and we wish to find the K ≤ 100 shortest paths. Since the graph is acyclic with a natural ordering to the vertices, Dynamic Programming is a good first approach.
Suppose that we knew the K shortest paths starting at each vertex i for i ≥ l and going downhill to the barn at vertex N. Then, to compute the K shortest such paths beginning at vertex i-1, we consider all outgoing edges from vertex i-1. Suppose that vertex i-1 has d outgoing edges. The ends of these d edges are all larger than i-1 and we have computed the K shortest paths from each of these. We can consider prepending vertex i-1 to all of these dK paths. The best K paths starting at vertex i-1 will come from these dK paths. We can efficiently compute a sorted list of the K best paths starting at vertex i-1 by merging these d lists of K items. This requires d*K time at each vertex. Summing over all vertices yields O(MK) time. With M=10,000 and K=100, this will be around 1,000,000 operations, which works. 官方程序
#include <stdio.h>
const int BIG = 1000000000;
const int MAXN = 2000;
const int MAXE = 20000;
const int MAXK = 200;
int n,e,k;
int ea[MAXE];
int eb[MAXE];
int elen[MAXE];
int d[MAXN];
int *out[MAXN];
int *len[MAXN];
int path[MAXN][MAXK];
int ei[MAXN];
int main() {
FILE *fin;
fin = fopen("cowjog.in", "r");
fscanf(fin, "%d %d %d", &n, &e, &k);
for(int i = 0; i < n; ++i){
d[i] = 0;
}
for(int i = 0; i < e; ++i){
int a,b,l;
fscanf(fin, "%d %d %d", &b, &a, &l);
--a; --b;
++d[a];
}
fclose(fin);
out[0] = &eb[0];
len[0] = &elen[0];
for(int i = 1; i < n; ++i){
out[i] = out[i-1] + d[i-1];
len[i] = len[i-1] + d[i-1];
}
fin = fopen("cowjog.in", "r");
fscanf(fin, "%d %d %d", &n, &e, &k);
for(int i = 0; i < n; ++i){
d[i] = 0;
}
for(int i = 0; i < e; ++i){
int a,b,l;
fscanf(fin, "%d %d %d", &b, &a, &l);
--a; --b;
out[a][d[a]] = b;
len[a][d[a]] = l;
++d[a];
}
fclose(fin);
path[n-1][0] = 0;
for(int i = 1; i < k; ++i){
path[n-1][i] = BIG;
}
for(int i = n-2; i >= 0; --i){
for(int j = 0; j < d[i]; ++j){
ei[j] = 0;
}
for(int j = 0; j < k; ++j){
int best_m = 0;
int best_d = BIG;
for(int m = 0; m < d[i]; ++m){
if(len[i][m] + path[out[i][m]][ei[m]] < best_d) {
best_m = m;
best_d = len[i][m] + path[out[i][m]][ei[m]];
}
}
path[i][j] = best_d;
++ei[best_m];
}
}
FILE *fout = fopen("cowjog.out", "w");
for(int i = 0; i < k; ++i){
fprintf(fout, "%dn", (path[0][i] == BIG) ? -1 : path[0][i]);
}
fclose(fout);
return(0);
}
上次修改時間 2017-05-22