TransfurTrain.配列のサイズを間違えてTrainがねこBusになりました。
#include<stdio.h> #include<algorithm> #include<queue> #include<map> #include<vector> #include<string> using namespace std; char str[16]; map<string,int> m; vector<pair<int,int> >g[100000]; vector<pair<int,int> >ijk[50000]; pair<int,int> IJK[100000]; vector<int> num[50000]; vector<int> dist[50000]; vector<int> vis[50000]; int VIS[100000]; struct wolf{ int cost; int chg; int L; int Y; wolf(){} wolf(int a,int b,int c,int d){ cost=a; chg=b; L=c; Y=d; } }; inline bool operator<(const wolf&a,const wolf&b){ if(a.cost!=b.cost)return a.cost>b.cost; return a.chg>b.chg; } int main(){ int a,b; scanf("%d%d",&a,&b); int v=0; scanf("%s",str); string S=str; scanf("%s",str); string T=str; m[S]=v++; m[T]=v++; for(int i=0;i<a;i++){ int c; scanf("%d",&c); for(int j=0;j<c;j++){ scanf("%s",str); string STR=str; if(m.count(STR)==0)m[STR]=v++; ijk[i].push_back(make_pair(999999999,999999999)); num[i].push_back(m[STR]); vis[i].push_back(0); g[m[STR]].push_back(make_pair(i,j)); } for(int j=0;j<c-1;j++){ int d; scanf("%d",&d); dist[i].push_back(d); } } for(int i=0;i<v;i++)IJK[i]=make_pair(999999999,999999999); priority_queue<wolf> Q; Q.push(wolf(0,0,-1,m[S])); IJK[m[S]]=make_pair(0,0); while(Q.size()){ wolf at=Q.top(); Q.pop(); if(at.L==-1){ if(VIS[at.Y])continue; VIS[at.Y]=1; }else{ if(vis[at.L][at.Y])continue; vis[at.L][at.Y]=1; } if(at.L==-1){ for(int i=0;i<g[at.Y].size();i++){ int I=g[at.Y][i].first; int J=g[at.Y][i].second; if(!vis[I][J]&&ijk[I][J]>IJK[at.Y]){ ijk[I][J]=IJK[at.Y]; Q.push(wolf(at.cost,at.chg,I,J)); } } }else{ int N=num[at.L][at.Y]; if(!VIS[N]&&IJK[N]>make_pair(at.cost+b,at.chg+1)){ IJK[N]=make_pair(at.cost+b,at.chg+1); Q.push(wolf(IJK[N].first,IJK[N].second,-1,N)); } if(at.Y&&!vis[at.L][at.Y-1]&&ijk[at.L][at.Y-1]>make_pair(at.cost+dist[at.L][at.Y-1],at.chg)){ ijk[at.L][at.Y-1]=make_pair(at.cost+dist[at.L][at.Y-1],at.chg); Q.push(wolf(at.cost+dist[at.L][at.Y-1],at.chg,at.L,at.Y-1)); } if(at.Y<dist[at.L].size()&&!vis[at.L][at.Y+1]&&ijk[at.L][at.Y+1]>make_pair(at.cost+dist[at.L][at.Y],at.chg)){ ijk[at.L][at.Y+1]=make_pair(at.cost+dist[at.L][at.Y],at.chg); Q.push(wolf(at.cost+dist[at.L][at.Y],at.chg,at.L,at.Y+1)); } } } if(IJK[m[T]].first==999999999)printf("-1\n"); else printf("%d %d\n",IJK[m[T]].first-b,IJK[m[T]].second-1); }