>Description

给出一张有边权的有向图，问在所有从0到1的最短路中，最少花费的一条路花费为多少

---

>解题思路

考虑到“顶点最多有100个；边最多有1000条”，可以简单地解决这道题
先用floyed跑出从0到1的最短路是多少（也可以用spfa，不过floyed不会爆而且还比较好打所以用floyed）
然后再用spfa跑最少花费，添加一些条件，判断是否为最短路就行

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 110
#define M 1010
#define LL long long
using namespace std;

queue<int> q;
struct edge
{
	int to, next, c;
} e[M];
int n, m, cnt, h[N], p[N];
LL ans, c[N], d[N][N];
bool mark[N];

void add (int u, int v, int w)
{
	e[++cnt] = (edge){v, h[u], w};
	h[u] = cnt;
}

int main()
{
	freopen ("paths.in", "r", stdin);
	freopen ("paths.out", "w", stdout);
	
	memset (c, 0x7f, sizeof (c));
	memset (p, 0x7f, sizeof (p));
	ans = c[0];
	int u, v, w;
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d%d", &u, &v, &w);
		u++, v++;
		add (u, v, w);
		d[u][v] = 1;
	}
	for (int i = 1; i <= n; i++) d[i][i] = 0;
	for (int k = 1; k <= n; k++)
	  for (int i = 1; i <= n; i++)
	    for (int j = 1; j <= n; j++)
	      if (i != j && j != k && i != k)
	        if (d[i][k] != 0 && d[k][j] != 0)
	        {
	        	if (d[i][j] == 0) d[i][j] = d[i][k] + d[k][j];
	        	else d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
			}
	q.push (1);
	mark[1] = 1;
	c[1] = p[1] = 0; //c表示花费，p表示路径长
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		mark[u] = 0;
		for (int i = h[u]; i; i = e[i].next)
		{
			v = e[i].to;
			if (c[u] + (LL)e[i].c > c[v]) continue;
			if (p[u] + 1 > p[v]) continue;
			if (p[v] == p[u] + 1)
			  c[v] = min (c[v], c[u] + (LL)e[i].c);
			else c[v] = c[u] + (LL)e[i].c;
			p[v] = p[u] + 1;
			if (v == 2 && p[v] == d[1][2])
			  ans = min (ans, c[v]);
			if (!mark[v])
			{
				q.push(v);
				mark[v] = 1;
			}
		}
	}
	printf ("%lld", ans);
	return 0;
}