Submission #1321840
Source Code Expand
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS 1e-9
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
typedef pair<int, pair<int, int> > Edge;
typedef vector<Edge> vE;
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > pqlE;
void Dijkstra(vvP graph, int start, vi &cost) {
//vi prev(graph.size());
pqlP Q;
fill(cost.begin(), cost.end(), INF);
cost[start] = 0;
Q.push(mp(0, start)); // (cost, index)
while (!Q.empty()) {
P pos = Q.top();
Q.pop();
rep(i, graph[pos.second].size()) {
if (cost[graph[pos.second][i].first] > cost[pos.second] + graph[pos.second][i].second) {
cost[graph[pos.second][i].first] = cost[pos.second] + graph[pos.second][i].second;
Q.push(mp(cost[graph[pos.second][i].first], graph[pos.second][i].first));
//prev[graph[pos.second][i].first] = pos.second;
}
}
}
}
int main() {
int N, M, R, T;
cin >> N >> M >> R >> T;
vvP G(N);
rep(i, M) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
G[a].push_back(mp(b, c));
G[b].push_back(mp(a, c));
}
int ans = 0;
rep(i, N) {
vi dist(N);
Dijkstra(G, i, dist);
vP list;
rep(j, N) {
if (j != i) {
list.push_back(mp(dist[j] * R, 1));
list.push_back(mp(dist[j] * T, 0));
}
}
sort(all(list));
int num = 0;
rep(i, list.size()) {
if (list[i].second == 0) {
ans += num;
}
num += list[i].second;
}
if (R < T) {
ans -= N - 1;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
furuya1223 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2597 Byte |
Status |
WA |
Exec Time |
1883 ms |
Memory |
728 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample-01.txt, subtask0_sample-02.txt |
All |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample-01.txt |
AC |
1 ms |
256 KB |
subtask0_sample-02.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
10 ms |
256 KB |
subtask1_06.txt |
AC |
13 ms |
256 KB |
subtask1_07.txt |
AC |
45 ms |
384 KB |
subtask1_08.txt |
AC |
58 ms |
384 KB |
subtask1_09.txt |
AC |
524 ms |
512 KB |
subtask1_10.txt |
AC |
532 ms |
384 KB |
subtask1_11.txt |
AC |
212 ms |
384 KB |
subtask1_12.txt |
WA |
1725 ms |
616 KB |
subtask1_13.txt |
WA |
1724 ms |
616 KB |
subtask1_14.txt |
WA |
1883 ms |
728 KB |
subtask1_15.txt |
AC |
1227 ms |
584 KB |
subtask1_16.txt |
WA |
1862 ms |
632 KB |