Submission #3044415
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000
using namespace std;
typedef pair<int, int> Pii;
template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);
#define MAX_V 100000
int V;
struct edge{int to, cost;};
vector<edge> G[MAX_V];
void add_edge(int from, int to, int cost){
G[from].push_back(edge({to, cost}));
}
void add_edge2(int v1, int v2, int cost){
G[v1].push_back(edge({v2, cost}));
G[v2].push_back(edge({v1, cost}));
}
int d[MAX_V];
int d2[MAX_V];
void dijkstra(int s, int t){
priority_queue<Pii, vector<Pii>, greater<Pii>> que;
fill(d, d + V, INF);
d[s] = 0;
que.push(Pii(0, s));
while(!que.empty()){
Pii p = que.top(); que.pop();
int v = p.second;
if(v == t) return;
if(d[v] < p.first) continue;
REP(i, G[v].size()){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(Pii(d[e.to], e.to));
}
}
}
}
signed main(){
int r = 1000000000 + 7;
int N, M;
cin >> N >> M;
V = N;
int S, T;
cin >> S >> T;
S--; T--;
int U, V, D;
REP(i, M){
cin >> U >> V >> D;
add_edge2(U - 1, V - 1, D);
}
vector<Pii> d0(N);
dijkstra(S, -1);
REP(i, N) d0[i] = Pii(d[i], i);
SORT(d0);
vector<int> dS(N, 0);
dS[S] = 1;
FOR(i, 1, N){
int v = d0[i].second;
int c = d0[i].first;
dS[v] = 0;
REP(k, G[v].size()){
if(G[v][k].cost + d[G[v][k].to] == c) dS[v] = (dS[v] + dS[G[v][k].to]) % r;
}
}
dijkstra(T, -1);
REP(i, N) d2[i] = d[i];
REP(i, N) d0[i] = Pii(d[i], i);
SORT(d0);
vector<int> dT(N, 0);
dT[T] = 1;
FOR(i, 1, N){
int v = d0[i].second;
int c = d0[i].first;
dT[v] = 0;
REP(k, G[v].size()){
if(G[v][k].cost + d[G[v][k].to] == c) dT[v] = (dT[v] + dT[G[v][k].to]) % r;
}
}
int ans = (dS[T] * dT[S]) % r;
//頂点上で会うのを除く
int n = 0;
dijkstra(S, -1);
REP(i, N){
if(d[i] * 2 == d[T]){
int tmp = (dS[i] * dT[i]) % r;
n = (n + (tmp * tmp)) % r;
}
}
ans = (ans + (r - n)) % r;
//辺上で会うのを取り除く
n = 0;
REP(vS, N){
REP(k, G[vS].size()){
int vT = G[vS][k].to;
if(d[vS] + d2[vT] + G[vS][k].cost == d[T] &&llabs(d[vS] - d2[vT]) < G[vS][k].cost){
int tmp = (dS[vS] * dT[vT]) % r;
n = (n + (tmp * tmp)) % r;
}
}
}
ans = (ans + (r - n)) % r;
cout << ans;
return 0;
}
template<typename T>
void readvec(vector<T> &a){
REP(i, a.size()){
cin >> a[i];
}
}
void readindex(vector<int> &a){
REP(i, a.size()){
cin >> a[i];
a[i]--;
}
}
Submission Info
Submission Time |
|
Task |
E - Avoiding Collision |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3348 Byte |
Status |
AC |
Exec Time |
345 ms |
Memory |
20280 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample01.txt, sample02.txt, sample03.txt, sample04.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
307 ms |
20280 KB |
02.txt |
AC |
328 ms |
19256 KB |
03.txt |
AC |
327 ms |
18144 KB |
04.txt |
AC |
324 ms |
18008 KB |
05.txt |
AC |
322 ms |
19136 KB |
06.txt |
AC |
245 ms |
15396 KB |
07.txt |
AC |
306 ms |
19260 KB |
08.txt |
AC |
160 ms |
12544 KB |
09.txt |
AC |
325 ms |
18132 KB |
10.txt |
AC |
317 ms |
17824 KB |
11.txt |
AC |
345 ms |
18200 KB |
12.txt |
AC |
344 ms |
17956 KB |
13.txt |
AC |
305 ms |
19268 KB |
14.txt |
AC |
302 ms |
19260 KB |
15.txt |
AC |
321 ms |
19388 KB |
16.txt |
AC |
326 ms |
19284 KB |
17.txt |
AC |
324 ms |
19396 KB |
18.txt |
AC |
321 ms |
19288 KB |
sample01.txt |
AC |
2 ms |
2560 KB |
sample02.txt |
AC |
2 ms |
2560 KB |
sample03.txt |
AC |
2 ms |
2560 KB |
sample04.txt |
AC |
2 ms |
2560 KB |