Submission #00360

ソースコード

#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:04
言語	C++11
状態	Wrong Answer
得点	0
ソースコード長	1156 Byte
最大実行時間	223 ms
最大メモリ使用量	18296 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
!test01.txt	WA	19 ms	2784 KB	1	2
!test02.txt	WA	18 ms	2828 KB	1	2
mesh_01.txt	WA	223 ms	7224 KB	1
mesh_02.txt	WA	206 ms	7312 KB	1
randomL_01.txt	WA	183 ms	11908 KB	1
randomL_02.txt	WA	187 ms	13540 KB	1
randomL_03.txt	WA	178 ms	15032 KB	1
randomL_04.txt	WA	182 ms	16660 KB	1
randomL_05.txt	WA	175 ms	18296 KB	1
randomS_01.txt	WA	25 ms	11240 KB	1	2
randomS_02.txt	WA	19 ms	11192 KB	1	2
randomS_03.txt	WA	23 ms	11284 KB	1	2
treeL_01.txt	WA	148 ms	16620 KB	1
treeL_02.txt	WA	142 ms	18252 KB	1
treeS_01.txt	WA	22 ms	13876 KB	1	2
treeS_02.txt	WA	22 ms	13740 KB	1	2