Submission #18082

ソースコード

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m,c,s,g,d[11][101],ans=1e9,a,b,f;
vector<pair<int,int> >G[101];
queue<pair<int,int> >P;
main()
{
        cin>>c>>n>>m>>s>>g;
        for(int i=0;i<m;i++)
        {
                cin>>a>>b>>f;
                G[a].push_back(make_pair(b,f));
                G[b].push_back(make_pair(a,f));
        }
        for(int i=0;i<=c;i++)for(int j=0;j++<n;)d[i][j]=1e9;
        P.push(make_pair(s,d[0][s]=0));
        while(!P.empty())
        {
                int u=P.front().first,cc=P.front().second;P.pop();
                for(int i=0;i<G[u].size();i++)
                {
                        int v=G[u][i].first,cost=G[u][i].second;
                        if(d[cc][v]>d[cc][u]+cost)
                        {
                                d[cc][v]=d[cc][u]+cost;
                                P.push(make_pair(v,cc));
                        }
                        if(cc<c&&d[cc+1][v]>d[cc][u]+cost/2)
                        {
                                d[cc+1][v]=d[cc][u]+cost/2;
                                P.push(make_pair(v,cc+1));
                        }
                }
        }
        for(int i=0;i<=c;i++)ans=min(ans,d[i][g]);
        cout<<ans<<endl;
}

ステータス

項目	データ
問題	0717 - 高速バス
ユーザー名	kotatsugame
投稿日時	2017-05-27 14:47:11
言語	C++11
状態	Accepted
得点	5
ソースコード長	891 Byte
最大実行時間	15 ms
最大メモリ使用量	700 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.txt	AC	11 ms	480 KB	1
input02.txt	AC	12 ms	428 KB	1
input03.txt	AC	10 ms	644 KB	1
input04.txt	AC	15 ms	592 KB	1
input05.txt	AC	10 ms	676 KB	1
input06.txt	AC	13 ms	628 KB	1
input07.txt	AC	14 ms	568 KB	1
input08.txt	AC	11 ms	632 KB	1
input09.txt	AC	11 ms	700 KB	1
input10.txt	AC	14 ms	640 KB	1