Dutor

const int MAXINT = 0xFFFF; //~ 不可达的路径长度上限
struct Node
{
    Node(): w(MAXINT){}
    int src, //~ 最短路径上的上一个顶点
        w; //~ 到该节点的路径长度
};
struct Edge
{
    Edge(){}
    Edge(int f, int t): from(f), to(t){}
    int from,
        to;
};
int
main(int argc, char **argv)
{
    vector<vector<int> > Adj;
    int n, // 顶点数
        m, //~ 边数
        from,
        to,
        w,
        start; //~ 源点
    cin>>n;
    vector<Node> Dist(n);
    for(int i = 0; i < n; ++i)
    {
        Adj.push_back(vector<int>(n, MAXINT));
        Adj[i][i] = 0;
    }
    cin>>m;
    vector<Edge> Edges;
    for(int i = 0; i < m; ++i)
    {
        cin>>from>>to>>w;
        Adj[from][to] = w;
        Edges.push_back(Edge(from, to));
    }
    cin>>start; //~ 从顶点start开始的最短路径
    Dist[start].w = 0; //~
    bool flag = true;
    for( int i = 0; i < n - 1; ++i)
    {
        for(int j = 0; j < Edges.size(); ++j)
        {
            from = Edges[j].from;
            to = Edges[j].to;
            if(Dist[from].w == MAXINT || Adj[from][to] == MAXINT)
                continue;
            if(Dist[from].w + Adj[from][to] < Dist[to].w)
            {
                Dist[to].w = Dist[from].w + Adj[from][to];
                Dist[to].src = from;
                flag = false;
            }
        }
        if(flag == true)
            break;
        else
            flag = true;
    }
    //~ 检测有无负环路
    for(int j = 0; j < Edges.size(); ++j)
    {
        from = Edges[j].from;
        to = Edges[j].to;
        if(Dist[from].w == MAXINT || Adj[from][to] == MAXINT)
            continue;
        if(Dist[from].w + Adj[from][to] < Dist[to].w)
        {
            cout<<"Negative Length Cycle Detected!"<<endl;
            return 1;
        }
    }
    //~ 下面代码供测试用
    while(cin>>to)
    {
        int rp = to;
        cout<<Dist[to].w<<" ";
        while(rp != start) //~ 反向输出路径
        {
            cout<<rp<<" <- ";
            if(Dist[to].w == MAXINT) break;
            rp = Dist[rp].src;
        }
        cout<<start<<endl;
    }
    return 0;
}