Submission #00361

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,int> PES;
typedef pair<int,int> P;
 
vector<P> vec[100005];
long long data[100005];
 
int n,m;
int f,s;
 
int main(){
  ios_base::sync_with_stdio(false);
  int a,b,c;
 
  cin >> n >> m;
  for(int i=0;i<=n;i++){
    data[i] = INT_MAX;
  }
  cin >> f >> s;
 
  for(int i=0;i<m;i++){
    cin >> a >> b >> c;
    vec[a].push_back(P(b,c));
    vec[b].push_back(P(a,c));
  }
   
  priority_queue<PES> que;
  que.push(PES(0,f));
  que.push(PES(0,s));
  data[f] = data[s] = 0;
   
  while(!que.empty()){
    PES now = que.top(); que.pop();
    long long cost = now.first;
    int pos = now.second;
    data[pos] = min(cost,data[pos]);
     
    if(data[pos] >= cost){
      for(int i=0;i<vec[pos].size();i++){
        int next = vec[pos][i].first;
        int ncost = vec[pos][i].second;
        if(data[next] > cost+ncost) {
          que.push(PES(cost+ncost,next));
          data[next] = cost+ncost;
        }
      }
    }
  }
   
  long long ans = 0;
  for(int i=1;i<=n;i++){
    ans += data[i];
    //cout << i << ' ' << data[i] << endl;
  }
   
  cout << ans << endl;
   
  return 0;
}

ステータス

項目	データ
問題	0004 - railway
ユーザー名	ei1612
投稿日時	2017-11-26 14:51:22
言語	C++11
状態	Wrong Answer
得点	0
ソースコード長	1173 Byte
最大実行時間	226 ms
最大メモリ使用量	10144 KB

セット

	セット	得点	Cases
1	ALL	0 / 80	*
2	partial_1	0 / 20	!, S*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
!test01.txt	AC	23 ms	2780 KB	1	2
!test02.txt	WA	25 ms	2696 KB	1	2
mesh_01.txt	WA	218 ms	7224 KB	1
mesh_02.txt	WA	226 ms	7188 KB	1
randomL_01.txt	WA	96 ms	9996 KB	1
randomL_02.txt	WA	98 ms	10088 KB	1
randomL_03.txt	WA	103 ms	10048 KB	1
randomL_04.txt	WA	98 ms	10144 KB	1
randomL_05.txt	WA	99 ms	9984 KB	1
randomS_01.txt	WA	23 ms	2928 KB	1	2
randomS_02.txt	WA	20 ms	2876 KB	1	2
randomS_03.txt	WA	31 ms	2960 KB	1	2
treeL_01.txt	WA	55 ms	7392 KB	1
treeL_02.txt	WA	51 ms	7360 KB	1
treeS_01.txt	WA	16 ms	2988 KB	1	2
treeS_02.txt	WA	19 ms	3108 KB	1	2