第13回日本情報オリンピック 予選 問題5 タクシー (Taxis) AOJ0596

深さ優先探索＋ダイクストラ

幅優先探索使ったほうがいいことにACしたあと気がついた。
まあ通れば勝ちでしょ...（震え声

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;
const int MAX_V = 5003;
int cost[MAX_V][MAX_V];
int cosn[5003][5003];
int d[MAX_V];
bool used[MAX_V];
int V;
int s[5003][2];
vector<int> vec[5003];

void dijkstra(int s){
	fill(d,d+V+1,INF);
	fill(used,used+V+1,false);
	d[s] = 0;
	while(true){
		int v = -1;
		for(int u = 1;u <= V;u++){
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		if(v == -1)break;
		used[v] = true;
		for(int u = 1;u <= V;u++){
			d[u] = min(d[u],d[v]+cost[v][u]);
		}
	}
}

void dfs(int from,int to,int nau){
	cost[from][to] = s[from][0];
	cosn[from][to] = nau;
	if(nau == s[from][1])return;
	for(int i = 0;i < vec[to].size();i++){
		int ne = vec[to][i];
		if(cost[from][ne] == INF || cosn[from][ne] > nau+1){
			dfs(from,ne,nau+1);
		}
	}
}

int main(){

	int k;
	cin >> V >> k;
	for(int i = 0;i <= V;i++){
		for(int j = 0;j <= V;j++){
			cost[i][j] = INF;
			cosn[i][j] = INF;
		}
	}
	for(int i = 1;i <= V;i++)cin >> s[i][0] >> s[i][1];

	for(int i = 0;i < k;i++){
		int a,b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for(int i = 1;i <= V;i++){
		for(int j = 0;j < vec[i].size();j++){
			int ne = vec[i][j];
			dfs(i,ne,1);
		}
	}
	dijkstra(1);
	cout << d[V] << endl;
	return 0;
}