题目描述

Description

众所周知，新世纪的科学很发达，于是Ray 和Raven 开始了星际探险，他们在宇宙中开辟了一片空间，建造了N 个空间站。这N 个空间站由一些单向的时空隧道连接，这些时空隧道都有一个穿越指数，穿过这些时空隧道，你可以走到未来或者回到过去，当然，这些都是由穿越指数决定的。有一天，Ray 和Raven 开始了一场比赛。他们要从一个空间站S 出发去另一个空间站T，先到的人获胜。Raven 一定会选一条能最快到达T 的路线。他希望Ray 输给他，所以事先在Ray 的飞船上设定了飞行路径，使得Ray 从S 到T 只能走一条特定的路径。但是，Ray 有对策，他有一台能够操纵时空隧道的机器，这台机器每次可以把某一条时空隧道的穿越指数增加或减少1，但是因为操纵机器很累，所以Ray 希望尽可能少改动，当然，如果改动后从某个空间站经过一系列的穿越可以在从这个空间站出发之前回到这个空间站，那么这样的改动是不允许的。修改之后，Raven 依然会走能最快到达终点的路线，所以Ray 是不可能赢的。但他请你帮助他确定改动时空隧道的方案，使得他能和Raven 同时到达T。

Input

输入的第一行包含两个整数N 和M，代表空间站的数目和时空隧道的数目。接下来M 行，每行三个整数u、v 和w，代表从空间站u 到空间站 v 有一条时空隧道，它的穿越指数是w。0 <= w <= 2000。空间站的编号是0 : : :N − 1。第M + 2 行包含一个整数p，代表Raven 在Ray 的飞船上设定的那条路径的空间站数。p <= N。第M + 3 行包含p 个互不相同的数，表示那条路径上的空间站的编号，第一个数是S，最后一个数是T。

Output

输出的第一行包含一个整数，表示Ray 走那条路径并且能够赢得比赛的情况下操纵时间机器的最小次数。

Sample Input

3 3
0 1 1
1 2 2
0 2 1
30
1 2

Sample Output

2

题目分析

啥? 为啥交的人这么少？ 是我naive么
难道答案不是给定的路径长度-最短路长度么?

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tot;
int head[6000],to[60000],net[60000],val[60000];
void add(int x,int y,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;
}
int dis[6000];
int num[6000],ans;
bool vis[6000];
void spfa()
{
    queue<int>q;
    memset(dis,0x3f,sizeof dis);
    q.push(num[1]),dis[num[1]]=0;
    while(q.size())
    {
        int x=q.front();
        q.pop(),vis[x]=0;
        for(int i=head[x];i;i=net[i])
            if(dis[to[i]]>dis[x]+val[i])
            {
                dis[to[i]]=dis[x]+val[i];
                if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int x,y,c,i=1;i<=m;i++)
        scanf("%d%d%d",&x,&y,&c),add(++x,++y,c);
    scanf("%d",&num[0]);
    for(int i=1;i<=num[0];i++) scanf("%d",&num[i]),num[i]++;
    spfa();
    for(int i=2;i<=num[0];i++)
        for(int j=head[num[i-1]];j;j=net[j])
            if(to[j]==num[i]) { ans+=val[j]; break; }
    printf("%d",ans-dis[num[num[0]]]);
    return 0;
}