[JSOI2015]地铁线路

题意：
有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？

思路：
最短路+拓扑+dp
一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点记录从起点到终点，另一个记录从终点到起点，从起点到终点使虚点对该路线的每一个节点连一条花费为0，时间为从该节点到起点的距离，每一个点连接一条到虚点的边，花费为1，时间为从该节点到起点的距离的相反数，从终点到起点使虚点对该路线的每一个节点连一条花费为0，时间为从该节点到终点的距离，每一个点连接一条到虚点的边，花费为1，时间为从该节点到终点的距离的相反数.这样图就建好了，然后开始跑最短路，获取只包含最短路的最短路图，这图一定是有向无环图，然后边拓扑边dp求出最大花费时间为多少。

代码:

#include<bits/stdc++.h>

#define ll long long
#define eps 1e-8

using namespace std;

const ll inf=1e9+7;

struct w
{
    int to, dis, cost;
}w;

map<string,int> ma;
string s;
int qi, zh, d[1000005];

vector<struct w> g[1000005], g1[1000005];

struct p
{
    int v, cost;
}p, p2;

bool operator<(struct p a,struct p b)
{
    return a.cost>b.cost;
}

int in[1000005];

void djk()
{
    fill(d,d+1000005,inf);
    d[qi]=0;
    p.v=qi;
    p.cost=0;
    priority_queue<struct p> q;
    q.push(p);
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        int v=p.v, t=p.cost;
        if(t>d[v])
        {
            continue;
        }
        for(int i=0;i<g[v].size();i++)
        {
            int u=g[v][i].to, cost=g[v][i].cost;
            if(d[u]>cost+t)
            {
                d[u]=t+cost;
                p2.cost=d[u];
                p2.v=u;
                q.push(p2);
            }
        }
    }
}

queue<int> q;
int dp[1000005];

void kp()
{
    fill(dp,dp+1000005,-inf);
    dp[qi]=0;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0;i<g1[v].size();i++)
        {
            int u=g1[v][i].to;
            in[u]--;
            dp[u]=max(dp[u],dp[v]+g1[v][i].dis);
            if(in[u]==0)
            {
                q.push(u);
            }
        }
    }
}

int main()
{
    int n, m;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        cin >> s;
        ma[s]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int ki;
        scanf("%d",&ki);
        for(int j=1;j<=ki;j++)
        {
            cin >> s;
            int v=ma[s];
            w.to=v;
            w.dis=j-1;
            w.cost=1;
            g[n+i].push_back(w);
            w.to=n+i;
            w.dis=-(j-1);
            w.cost=0;
            g[v].push_back(w);
            w.to=v;
            w.dis=ki-j;
            w.cost=1;
            g[n+m+i].push_back(w);
            w.to=n+i+m;
            w.dis=-(ki-j);
            w.cost=0;
            g[v].push_back(w);
        }
    }
    cin >> s;
    qi=ma[s];
    cin >> s;
    zh=ma[s];
    djk();
    if(d[zh]==inf)
    {
        printf("-1\n0\n");
        return 0;
    }
    cout << d[zh] << endl;
    for(int i=1;i<=n+2*m;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            int u=g[i][j].to;
            if(d[u]-d[i]==g[i][j].cost)
            {
                g1[i].push_back(g[i][j]);
                in[u]++;
            }
        }
    }
    for(int i=1;i<=n+2*m;i++)
    {
        if(in[i]==0)
        {
            q.push(i);
        }
    }
    kp();
    cout << dp[zh] << endl;
    return 0;
}