最长路径

最长路径

给定一个正权有向无环图和图中的两个顶点，请编写程序找出这两个顶点间的最长路径，若两点间存在多条最长路径，则输出字典序最小者。假定图中包含n个顶点，编号为0至n-1。

注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。

输入格式:

输入第一行为3个正整数n和e，分别为图的顶点数和边数，均不超过50。接下来e行表示每条边的信息，每行为3个整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。接下来1行为两个整数s和t，表示两个顶点编号。

输出格式:

输出顶点s到顶点t的字典序最小最长路径，路径中顶点编号用“->”间隔。如s和t不连通，则输出“none”。

思路：

拓扑排序+简单dp，由于正向取点时不同路径之间的长度不一致，字典序判断不易，可考虑反向加边

#include <bits/stdc++.h>
using namespace std;
int n,m,dp[2005],flag,head[2005],in[2005],fa[2005],si,r,s;
struct node{
    int to,next,x;
}p[2005]; 
void add(int x,int y,int k){
    p[++flag].to=y;
    p[flag].next=head[x];
    p[flag].x=k;
    head[x]=flag;
    in[y]++;
}
void tuopu(){
    queue<int> q;
    for(int i=0;i<n;i++){
        if(!in[i]) q.push(i);
        dp[i]=-1e9;
    } 
    dp[r]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=p[i].next){
            if(dp[x]+p[i].x>dp[p[i].to]){
                dp[p[i].to]=dp[x]+p[i].x;
                fa[p[i].to]=x;
            }
            else if(dp[x]+p[i].x==dp[p[i].to]){
                if(fa[p[i].to]>x)
                    fa[p[i].to]=x;
            }
            in[p[i].to]--;
            if(!in[p[i].to]&&s!=x) q.push(p[i].to);
        }
    }   
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(b,a,c);
    }
    cin>>s>>r;
    tuopu();
    if(dp[s]==-1e9) cout<<"none";
    else{
        while(r!=s){
            cout<<s<<"->";
            s=fa[s];
        }
        cout<<s;
    }
}