結果

提出番号 2211
提出者 ndifix
言語 C++
提出日時 2019-03-03 18:40:59
問題名 (2)Taxis
結果 TLE
点数 20%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8160KB
2 WA 0% 2ms 7872KB
3 TLE 0% 2793ms 22272KB
4 TLE 0% 20002ms 0KB
5 TLE 0% 20002ms 0KB

ソースコード

#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
using namespace std;
struct gragh{
	int V,E;
	vector<vector<pair<int,int>>> edge; //edge[from][i] ={to,cost}
	//only for 0-indexed 
	gragh(int v,int e,int *from,int *to,int *cost){
		V=v;E=e;	pair<int,int>p;
		for(int i=0;i<e;i++){
			//if(edge.size()<=from[i])edge.resize(from[i]+1);
			edge.resize(v);
			p.first=to[i];	p.second=cost[i];	edge[from[i]].push_back(p);
			p.first=from[i]; p.second=cost[i];	edge[to[i]].push_back(p);
		} }
	int dijkstra(int start,int goal){
		int done[V];	for(int i=0;i<V;i++)done[i]=0;	done[start]=1;
		int vertex[V];	for(int i=0;i<V;i++)vertex[i]=inf;	vertex[start]=0;
		queue<int> que;	que.push(start);
		int from, to, cost;
		while(que.size()!=0){
			from=que.front();
			for(int i=0; i<edge[from].size(); i++){
				to=edge[from][i].first;	cost=edge[from][i].second;
				if( vertex[to]>vertex[from]+cost){
					vertex[to]=vertex[from]+cost;
					que.push(to);
				}
			}
			que.pop();
		}
		return vertex[goal];	}
	int bellmanFord(){

	}};
int main(){
	int n,k; cin>>n>>k;
	int c[n],r[n]; for(int i=0;i<n;i++)cin>>c[i]>>r[i];
	int a[k],b[k]; for(int i=0;i<k;i++)cin>>a[i]>>b[i];

	int m[n][n]; for(int i=0;i<n;i++)for(int j=0;j<n;j++)m[i][j]=inf;
	for(int i=0;i<n;i++)m[i][i]=0;
	for(int i=0;i<k;i++){m[a[i]-1][b[i]-1]=1;	m[b[i]-1][a[i]-1]=1;}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)m[i][j]=min(m[i][j],m[i][k]+m[k][j]);
	
	vector<pair<pair<int,int>,int>> edge;
	pair<pair<int,int>,int> p;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(m[i][j]<=r[i]){
				p.first.first=i; p.first.second=j; p.second=c[i]; edge.push_back(p);
			}
		}
	}
	int f[edge.size()],t[edge.size()],C[edge.size()];
	for(int i=0;i<edge.size();i++){f[i]=edge[i].first.first; t[i]=edge[i].first.second; C[i]=edge[i].second;}
	gragh g(n, edge.size(), f, t, C);
	cout<<g.dijkstra(0,n-1)<<endl;
	return 0;
}