ソースコード
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int> >G[5000];
vector<int>GG[5000];
bool used[5000];
int c[5000],r[5000],n,k;
long d[5000];
main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>c[i]>>r[i];
}
for(int i=0;i<k;i++)
{
int u,v;cin>>u>>v;
u--,v--;
GG[u].push_back(v);
GG[v].push_back(u);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)used[j]=0;
queue<pair<int,int> >P;
P.push(make_pair(i,0));
used[i]=1;
while(!P.empty())
{
pair<int,int>p=P.front();
P.pop();
int u=p.first,x=p.second;
if(x>=r[i])continue;
for(int j=0;j<GG[u].size();j++)
{
if(used[GG[u][j]])continue;
int v=GG[u][j];
G[i].push_back(make_pair(v,c[i]));
used[v]=1;
P.push(make_pair(v,x+1));
}
}
}
for(int i=0;i<n;i++)d[i]=1e15;
priority_queue<pair<int,int> >P;
P.push(make_pair(0,0));
d[0]=0;
while(!P.empty())
{
pair<int,int>p=P.top();P.pop();
int u=p.second,x=-p.first;
if(d[u]<x)continue;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i].first,c=G[u][i].second;
if(d[v]>d[u]+c)
{
d[v]=d[u]+c;
P.push(make_pair(-d[v],v));
}
}
}
cout<<d[n-1]<<endl;
}