Acwing提高课图论补题 920. 最优乘车

题目 题意: 给定m个路线，n个点。m个路线是说，某条路线上左边的点可以花0的代价到达右边的点。但是从某条路线换到另一条路线就要花费1的代价。 思路: 用最笨的方法，建图。建图是mn2/2的。同一条路线上的花费为1. 最后结果为dist[n] - 1.因为第一次是不换乘的，从第二次开始就换乘了。 时间复杂度: O(mnn) 代码:

// Problem: 最优乘车
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/922/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 502;
const int INF = 0x3f3f3f3f;
int a[N][N];
int n,m,k,T;
#define fir(i,a,b) for(int i=a;im>>n;
	fir(i,1,n)
	fir(j,1,n)
	{
		if(i==j) a[i][j] = 0;
		else a[i][j] = 0x3f3f3f3f;
	}
	for(int i=0;i