Submission #00376

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repr(i, n) for(int i = n; i>=0; i--)
#define all(x) (x).begin(), (x).end()
#define INF 1001001001001001000
typedef long long ll;
typedef pair<int, int> p;
 
int n, m, a, b;
ll dist[2][100002], ans = 0;
vector<p> graph[100002];
 
void dijkstra(int s) {
        int cur = s == a ? 0 : 1;
        priority_queue<p, vector<p>, greater<p> > que;
        que.push(make_pair(s, 0));
        while (!que.empty()) {
                p temp = que.top();
                que.pop();
                int v = temp.first;
                if (dist[cur][v] < temp.second) continue;
                for (int i = 0; i < graph[v].size(); i++) {
                        p e = graph[v][i];
                        if (dist[cur][e.first] > dist[cur][v] + e.second) {
                                dist[cur][e.first] = dist[cur][v] + e.second;
                                que.push(make_pair(e.first, dist[cur][e.first]));
                        }
                }
        }
}
 
 
int main(void) {
        scanf("%d%d%d%d", &n, &m, &a, &b);
        for (int i = 0; i < 2; i++) {
                for (int j = 1; j <= n; j++) {
                        dist[i][j] = INF;
                }
        }
        dist[0][a] = 0;
        dist[1][b] = 0;
        for (int i = 0; i < m; i++) {
                int u, v, t;
                scanf("%d%d%d", &u, &v, &t);
                graph[u].push_back(make_pair(v, t));
                graph[v].push_back(make_pair(u, t));
        }
        dijkstra(a);
        dijkstra(b);
        for (int i = 1; i <= n; i++) {
                ans += min(dist[0][i], dist[1][i]);
        }
        printf("%lld\n", ans);
        return 0;
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
!test01.txt	AC	17 ms	2784 KB	1	2
!test02.txt	WA	19 ms	2840 KB	1	2
mesh_01.txt	WA	67 ms	7444 KB	1
mesh_02.txt	WA	75 ms	7504 KB	1
randomL_01.txt	WA	749 ms	18924 KB	1
randomL_02.txt	WA	718 ms	18796 KB	1
randomL_03.txt	WA	826 ms	23704 KB	1
randomL_04.txt	WA	743 ms	18304 KB	1
randomL_05.txt	WA	769 ms	18708 KB	1
randomS_01.txt	WA	17 ms	3152 KB	1	2
randomS_02.txt	WA	25 ms	2956 KB	1	2
randomS_03.txt	WA	27 ms	2888 KB	1	2
treeL_01.txt	WA	66 ms	8072 KB	1
treeL_02.txt	WA	64 ms	8036 KB	1
treeS_01.txt	WA	18 ms	2884 KB	1	2
treeS_02.txt	WA	18 ms	2880 KB	1	2