Tram（最短路）

Tram

板子题，对于每一个点，都存在一个与之免费的点，以及其余花费为1的点，那么建图时不联通的点的边的权值设为1，
而对于免费的点，其权值为0，联通不免费的点设置为1，这样跑一遍最短路，就可以解决问题。

//堆优化dijkstra
#include <iostream>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

const int N = 110;
struct Edge{
	int v, w, next;
}edge[N];

bool vis[N];
int tot, head[N], dist[N];
void add(int u, int v, int w){
	edge[tot].v = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot ++;
}
void dijkstra(int s){
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	memset(dist, INF, sizeof dist);
	memset(vis, 0, sizeof vis);
	pq.push(make_pair(0, s));
	while(pq.size()){
		int dis = pq.top().first;
		int id = pq.top().second;
		pq.pop();
		if(vis[id])
			continue;
		vis[id] = true;
		for(int i = head[id]; i != -1; i = edge[i].next){
			int w = edge[i].w;
			int to = edge[i].v;
			if(dist[to] > dis + w){
				dist[to] = dis + w;
				if(!vis[to])
					pq.push(make_pair(dist[to], to));
			}
		}
	}
}
int main(){
	int n, a, b;
	cin >> n >> a >> b;
	memset(head, -1, sizeof head);
	for(int i = 1; i <= n; i ++){
		int k, x;
		cin >> k;
		for(int j = 1; j <= k; j ++){
			cin >> x;
			if(j == 1)
				add(i, x, 0);
			else
				add(i, x, 1);
		}
	}
	dijkstra(a);
	if(dist[b] >= INF / 2)
		cout << -1 << endl;
	else
		cout << dist[b] << endl;
	return 0;
}

//floyd
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
int w[N][N];
int n;

void floyd(){
	for(int k = 1; k <= n; k ++)
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n; j ++)
				if(w[i][j] > w[i][k] + w[k][j])
					w[i][j] = w[i][k] + w[k][j]; 
}
int main(){
	int a, b;
	cin >> n >> a >> b;
	memset(w, 0x3f3f3f3f, sizeof w);
	for(int i = 1; i <= n; i ++){
		int k, x;
		cin >> k;
		for(int j = 1; j <= k; j ++){
			cin >> x;
			if(j == 1)
				w[i][x] = 0;
			else
				w[i][x] = 1;
		}
	}
	floyd();
	if(w[a][b] == 0x3f3f3f3f)
		cout << -1 << endl;
	else
		cout << w[a][b] << endl;
	return 0;
}