---
title: DAG 找最長路徑
tags: 演算法
---
## DAG 找最長路徑

### TIPS
>直接做 Bellman-Ford 然後把所有 weight 乘上 -1
> 算出來的 最短路徑再乘上 -1 即可

> 就是這麼簡單!

### 做法 - [Bellman-Ford 演算法](https://hackmd.io/@andy010629/Bellman-Ford)
---

### 相關題目
UVa 10000
(基本題 直接找最常路和結束點即可)

#include <iostream>
#include <queue>
#include <cmath>
#define mpair pair<int,int>
using namespace std;

int main()
{
    int v,r=1;
    while(cin>>v,v){
        int spt;
        cin>>spt;
        vector<vector<int> > gp(v+1);
        vector<bool> visted(v+1);
        int s,e;
        while(cin>>s>>e,s||e){
            gp[s].push_back(e);
        }
        
        queue<int> spfa;
        vector<int> vst(v+1),dist(v+1,0);
        vector<bool> inqueue(v+1);
        dist[0] = 0;
        int ans = 0, ansrt = spt;
        spfa.push(spt);
        while (!spfa.empty()) {
            int tmp = spfa.front();
            spfa.pop();
            vst[tmp]++;
            if (vst[tmp] > v) {
                break;
            }
            inqueue[tmp] = false;
            for (int ele :gp[tmp]) {
                if (dist[tmp] - 1 <= dist[ele]) {
                    dist[ele] = dist[tmp] - 1;
                    if(dist[ele]<=ans){
                        ans = dist[ele];
                    }
                    if (!inqueue[ele]) {
                        spfa.push(ele);
                        inqueue[ele] = true;
                    }
                }
            }
        }
        for(int i=0;i<=dist.size();i++)
            if(dist[i]==ans){
                ansrt=i;
                break;
            }
        cout<<"Case "<<r++<<": The longest path from "<<spt<<" has length "<<-ans<<", finishing at "<<ansrt<<".\n\n";
    }
    return 0;
}