這是一個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);
}