Submission #2036319


Source Code Expand

Copy
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"



const int DEBUG = 0;

using namespace std;
typedef long long int lint;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
const lint mod = 1e9 + 7;

const lint inf = 1e18;

lint sq(lint x) { return x * x % mod; }

const int N = 100100;
int n;
vector<pil> edges[N];

pll add(pll a, pll b) {
  if (a.first != b.first) return min(a,b);
  return pll(a.first,(a.second+b.second)%mod);
}
pll mul(pll a,pll b){
  return pll(a.first+b.first,a.second*b.second%mod);
}


vector<pll> calc(int s) {
  vector<pll> dp(n, pll(inf, 0));
  vector<bool> vis(n, false);
  priority_queue<pli, vector<pli> , greater<pli> > que;
  dp[s] = pll(0, 1);
  que.push(pli(0, s));
  while (not que.empty()) {
    pli vd = que.top(); que.pop();
    int v = vd.second;
    if (vis[v]) continue;
    vis[v] = true;
    REP(i, 0, edges[v].size()) {
      pil wc = edges[v][i];
      int w = wc.first;
      lint c = wc.second;
      dp[w]=add(dp[w],mul(dp[v],pll(c,1)));
      que.push(pli(dp[w].first,w));
    }
  }
  return dp;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int m, s, t;
  cin >> n >> m >> s >> t;
  s--, t--;
  REP(i, 0, m) {
    int u, v, d;
    cin >> u >> v >> d;
    u--, v--;
    edges[u].push_back(pil(v, d));
    edges[v].push_back(pil(u, d));
  }
  vector<pll> sol_s, sol_t;
  sol_s = calc(s);
  sol_t = calc(t);
  if (DEBUG) {
    cerr << "dp:";
    REP(i, 0, n) cerr << " " << sol_s[i].second;
    cerr << endl;
    cerr << "dp2:";
    REP(i, 0, n) cerr << " " << sol_t[i].second;
    cerr << endl;
  }
  lint ans = sq(sol_s[t].second);
  REP(i, 0, n) {
    if (sol_s[i].first + sol_t[i].first != sol_s[t].first) continue;
    if (2 * sol_s[i].first == sol_s[t].first) {
      ans += mod - sq(sol_s[i].second * sol_t[i].second % mod);
      ans %= mod;
    }
    if (2 * sol_s[i].first < sol_s[t].first) {
      REP(j, 0, edges[i].size()) {
	pil wc = edges[i][j];
	int w = wc.first;
	lint c = wc.second;
	if (sol_s[i].first + c + sol_t[w].first != sol_s[t].first) continue;
	if (2 * sol_s[w].first > sol_s[t].first) {
	  ans += mod - (sq(sol_s[i].second * sol_t[w].second % mod) % mod);
	  ans %= mod;
	}
      }
    }
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task E - Avoiding Collision
User kirika_comp
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2796 Byte
Status
Exec Time 235 ms
Memory 19144 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt, sample04.txt
All 700 / 700 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 230 ms 18960 KB
02.txt 235 ms 19088 KB
03.txt 213 ms 16884 KB
04.txt 210 ms 16452 KB
05.txt 233 ms 19144 KB
06.txt 150 ms 13824 KB
07.txt 223 ms 17892 KB
08.txt 70 ms 11008 KB
09.txt 214 ms 16896 KB
10.txt 214 ms 16844 KB
11.txt 212 ms 16976 KB
12.txt 209 ms 16560 KB
13.txt 224 ms 18020 KB
14.txt 224 ms 17892 KB
15.txt 224 ms 18060 KB
16.txt 223 ms 17940 KB
17.txt 223 ms 18064 KB
18.txt 230 ms 17944 KB
sample01.txt 2 ms 2560 KB
sample02.txt 2 ms 2560 KB
sample03.txt 2 ms 2560 KB
sample04.txt 2 ms 2560 KB