Submission #29635

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
typedef pair<P,P>Q;
int c,n,m,s,g;
int min_cost[101][11];
vector<P>node[101];
int INF=(1<<30);
int main(){
  cin>>c>>n>>m>>s>>g;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=10;j++){
      min_cost[i][j]=INF;
    }
  }
  for(int i=0;i<m;i++){
    int a,b,cost;
    cin>>a>>b>>cost;
    node[a].push_back(P(b,cost));
    node[b].push_back(P(a,cost));
  }
  priority_queue<Q,vector<Q>,greater<Q> >pq;
  pq.push(Q(P(0,s),P(0,0)));
  while(!pq.empty()){
    Q now=pq.top();pq.pop();
    int cost=now.first.first;
    int pos=now.first.second;
    int cnt=now.second.first;
    for(int i=0;i<node[pos].size();i++){
      int next=node[pos][i].first;
      int ncost=node[pos][i].second;
      if(cost+ncost<min_cost[next][cnt]){
        pq.push(Q(P(cost+ncost,next),P(cnt,0)));
        min_cost[next][cnt]=cost+ncost;
      }
      if(cost+ncost/2<min_cost[next][cnt+1]&&cnt<c){
        pq.push(Q(P(cost+ncost/2,next),P(cnt+1,0)));
        min_cost[next][cnt+1]=cost+ncost/2;
      }
    }
  }
  int ans=INF;
  for(int i=0;i<=c;i++)ans=min(ans,min_cost[g][i]);
  cout<<ans<<endl;
  return(0);
}

ステータス

項目	データ
問題	0717 - 高速バス
ユーザー名	r1705
投稿日時	2017-12-12 15:31:30
言語	C++11
状態	Accepted
得点	5
ソースコード長	1176 Byte
最大実行時間	37 ms
最大メモリ使用量	644 KB

セット

	セット	得点	Cases
1	ALL	5 / 5	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.txt	AC	37 ms	480 KB	1
input02.txt	AC	19 ms	428 KB	1
input03.txt	AC	15 ms	644 KB	1
input04.txt	AC	21 ms	460 KB	1
input05.txt	AC	23 ms	528 KB	1
input06.txt	AC	19 ms	456 KB	1
input07.txt	AC	24 ms	536 KB	1
input08.txt	AC	26 ms	584 KB	1
input09.txt	AC	22 ms	632 KB	1
input10.txt	AC	18 ms	576 KB	1