搭飛機

#include<bits/stdc++.h>
using namespace std;

#define INF 1e5

const int N = 220;
const int A = 55;
int n, q;
int g[N][N][A];

struct node{
	int v;
	int p;
	int a;

	node(int v, int p, int a): v(v), p(p), a(a){};
};

bool operator<(const node a, const node b){
	return a.p < b.p;
}


int cal(int u, int v){
	int dis[N][A];
	priority_queue<node> q;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			dis[i][j] = INF;
		}
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < A; j++){
			if(g[u][i][j]!=INF){
				dis[i][j]=g[u][i][j];
				q.push(node(i,dis[i][j],j));
				//cout << i << " " << j << " " << dis[i][j] << endl;
			}
		}
	}

	while(!q.empty()){
		int v=q.top().v, a=q.top().a;
		q.pop();
		for(int i = 0; i < N; i++){
			for(int j = 0; j < A; j++){
				if(g[v][i][j]!=INF){
					//cout << v << " " << i << " " << j << " " << g[v][i][j] << endl;
					int cost=dis[v][a]+g[v][i][j]+(a==j?0:5);
					if(cost < dis[i][j]){
						dis[i][j]=cost;
						q.push(node(i, dis[i][j], j));
					}
				}
			}
		}
		
	}
	int ans = INF;
	for(int i = 0; i < A; i++){
		ans = min (dis[v][i], ans);
	}
	return ans;

}



int main(){
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k < A; k++){
				g[i][j][k]=INF;
			}
		}
	}


	while(q--){
		string mode;
		cin >> mode;
		if(mode=="Add"){
			int u, v, p, a;
			cin >> u >> v >> p >> a;
			g[u][v][a]=p;

		}else if(mode=="Request"){
			int u, v, c;
			cin >> u >> v >> c;
			int ans = cal(u,v);
			if(ans > c) cout << -1 << endl;
			else cout << ans << endl;
		}else{
			int u, v, a;
			cin >> u >> v >> a;
			g[u][v][a]=INF;
		}
	}
}