Submission #2121216
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <limits>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
using ll = long long;
constexpr int MAX_N = 100000, mod = 1000000007;
constexpr ll INF = 1e17;
using P = std::pair<ll, int>;
struct edge
{ ll to, dist; };
int N, M;
int S, T;
std::vector<edge> G[MAX_N];
ll d1[MAX_N], d2[MAX_N];
ll dp1[MAX_N], dp2[MAX_N];
ll ans;
void dijkstra( int s, ll *ds, ll *dp )
{
std::priority_queue<P, std::vector<P>, std::greater<P>> pque;
pque.push( P( 0, s ) );
std::fill( (ll*)ds, (ll*)(ds+N), INF );
ds[s] = 0;
dp[s] = 1;
while( !pque.empty() )
{
P p = pque.top(); pque.pop();
ll dist = p.first, v = p.second;
if( ds[v] < dist )
continue;
for( auto &e : G[v] )
{
if( ds[e.to] > ds[v]+e.dist )
{
dp[e.to] = dp[v];
ds[e.to] = ds[v]+e.dist;
pque.push( P( ds[e.to], e.to ) );
}
else if( ds[e.to] == ds[v]+e.dist )
dp[e.to] = (dp[e.to] + dp[v]) % mod;
}
}
return;
}
int sqr( ll x )
{ return x%mod*x%mod; }
int main()
{
scanf( "%d%d%d%d", &N, &M, &S, &T );
--S; --T;
rep( i, M )
{
ll U, V, D;
scanf( "%lld%lld%lld", &U, &V, &D );
--U; --V;
G[U].push_back( (edge){ V, D } );
G[V].push_back( (edge){ U, D } );
}
dijkstra( S, d1, dp1 );
dijkstra( T, d2, dp2 );
ans = dp1[T]*dp1[T] % mod;
rep( i, N ) if( d1[i] == d2[i] && d1[i]+d2[i] == d1[T] )
ans = (ans - sqr( dp1[i]%mod*dp2[i]%mod ) + mod) % mod;
rep( i, N ) for( auto &e : G[i] )
{
int U = i, V = e.to, D = e.dist;
//if( 2*d1[U[i]] > d1[T] )
//std::swap( U[i], V[i] );
//if( 2*d1[U[i]] < d1[T] && 2*d1[V[i]] > d1[T] && d1[U[i]]+D[i] == d1[V[i]] )
if( 2*std::max( d1[U], d2[V] ) < d1[T] && d1[U]+D+d2[V] == d1[T] )
ans = (ans - sqr( dp1[U]%mod*dp2[V]%mod ) + mod) % mod;
}
printf( "%lld\n", ans );
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Avoiding Collision |
User |
As_sqr |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2050 Byte |
Status |
AC |
Exec Time |
158 ms |
Memory |
18772 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:63:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d%d%d%d", &N, &M, &S, &T );
^
./Main.cpp:68:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf( "%lld%lld%lld", &U, &V, &D );
^
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 |
138 ms |
18772 KB |
02.txt |
AC |
152 ms |
17992 KB |
03.txt |
AC |
147 ms |
16560 KB |
04.txt |
AC |
145 ms |
16364 KB |
05.txt |
AC |
152 ms |
17956 KB |
06.txt |
AC |
107 ms |
13844 KB |
07.txt |
AC |
143 ms |
17644 KB |
08.txt |
AC |
65 ms |
11008 KB |
09.txt |
AC |
143 ms |
16584 KB |
10.txt |
AC |
142 ms |
16384 KB |
11.txt |
AC |
158 ms |
16652 KB |
12.txt |
AC |
158 ms |
16464 KB |
13.txt |
AC |
144 ms |
17644 KB |
14.txt |
AC |
142 ms |
17644 KB |
15.txt |
AC |
157 ms |
17760 KB |
16.txt |
AC |
152 ms |
17640 KB |
17.txt |
AC |
152 ms |
17764 KB |
18.txt |
AC |
151 ms |
17768 KB |
sample01.txt |
AC |
2 ms |
3712 KB |
sample02.txt |
AC |
2 ms |
3712 KB |
sample03.txt |
AC |
2 ms |
3712 KB |
sample04.txt |
AC |
2 ms |
3712 KB |