ダイクストラ法

最短経路問題

問題　:　動作確認済み

(条件) 負の重みを持たない無向性グラフ

最短距離が更新されたときのみ、その頂点に隣接する辺の更新を行う

vector<vector<ll>> h(150, vector<ll>(150));//a,b間の距離
vector<ll> edge[108000]; // i 番目の島と繋がっている島すべて
ll dist[108000]; // 最短距離
ll n, m, k, s, x, a, b, c, j;

//ダイクストラ法
void dijkstra(ll start) {

	// 最短距離のみをifに通過させて、それ以外は余分な計算をしないため
	priority_queue<Pl, vector<Pl>, greater<Pl> > pq;
	fill(dist, dist + 108000, INF);

	dist[start] = 0;
	pq.push(Pl(0, start)); //最短距離、最初の島

	while (!pq.empty()) {
		Pl tmp = pq.top();pq.pop();
		ll from = tmp.second; // 島
		ll d = tmp.first;     // 最短距離

		if (dist[from] < d)continue; // 最短距離でない


		// ある島の最短距離と隣接する島をすべて探す
		for (ll i = 0;i < edge[from].size();i++) {
			ll to = edge[from][i];


			// ある島の仮の最短距離
			if (dist[to] > dist[from] + h[to][from]) {
				dist[to] = dist[from] + h[to][from];
				pq.push(Pl(dist[to], to));
				//cout << "p   " << h[to][from] << endl;
			}
		}
	}
}


int main() {

	cin >> n >> k; //島の数、クエリの数

	rep(i, 0, 150)rep(j, 0, 150) h[i][j] = INF;

	rep(i,0,k)
	{
	
		cin >> j;//判定

		if (j == 1)//追加
		{
			cin >> a >> b >> c;
			a--;b--;
			edge[a].push_back(b);//繋がり
			edge[b].push_back(a);

			h[a][b] = min(h[a][b], c);//距離
			h[b][a] = min(h[b][a], c);
			
			
		}
		else//計算
		{
			cin >> a >> b;//aからbまでを計算
			a--;b--;

			dijkstra(a);//aからの距離を計算

			if (dist[b] == INF) cout << "-1" << endl;//bまで行けない
			else cout << dist[b] << endl;
		}
		
	}
	

	return 0;
}