ソースコード
#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;
}