背景
话说上次YYB写强化的时候没有写好，于是hwz怒了。
描述
Hwz把YYB放到了一个迷宫之中，这个迷宫由n个节点构成，两个节点之间可能存在多条无向边，YYB的起点为1号节点，终点为n号节点。有m条无向边，对于每一条无向边，存在一个喋血值（∈N*，且≤100），即走过这条边的花费。另外，还有k个节点上有治疗药，即若YYB走到这个节点上时(不妨称这个点为治愈点)，他身上所累积的喋血值会归零。YYB希望以最小的喋血值走完迷宫。
格式
输入格式
第1行n,m,k分别表示有n个节点，m条无向边，以及k个治愈点。
第2行到m+1行 每一行有一个x,y,z表示x到y有一条喋血值为z的无向边
第n+2行 有k个整数，分别为治愈点的号数
PS：保证数据中没有负权回路。保证治愈点不重复。
输出格式
一行minblood 表示YYB走完迷宫的最小喋血值
当然，如果无法走出迷宫，输出Oh no!
样例1
样例输入1

3 3 1
1 2 100
2 3 1
1 3 3
2

样例输出1

1

提示
范围：
对于100%的数据
1≤n≤5000,1≤k≤n,1≤m≤25000
继续阅读 →

描述
输入数据给出一个有N(2 <= N <= 1,000)个节点，M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
格式
输入格式
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)
输出格式
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度.
样例1
样例输入1

6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

样例输出1

0
6
4
-3
-2
7

限制
Test5 5秒
其余 1秒
提示
做这道题时, 你不必为超时担心, 不必为不会算法担心, 但是如此“简单”的题目, 你究竟能ac么?
我TM都要死了，在八十中同学的好心帮助下才做出。
继续阅读 →