Submission #3233297
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<iomanip>
#include<cmath>
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<bitset>
#include<map>
// #include<unordered_map>
#include<set>
// #include<unordered_set>
#include<queue>
#include<deque>
#include<stack>
#include<functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define repi(i,a,b) for(ll i = (ll)(a) ; i < (ll)(b) ; i++)
#define repd(i,a,b) for(ll i = (ll)(a) ; i > (ll)(b) ; i--)
#define rd(x) cin >> x
#define wr(x) cout << x
#define wrln(x) cout << x << endl
#define ln() cout << endl
const ll MAX_10p5 = 100010;
const ll MAX_10p9 = 1000000010;
const ll MAX_10p18 = 1000000000000000010;
const ll MOD = 1000000007; // 998244353 , 1000000007
const ll m4x[4] = { 1,0,-1,0 };
const ll m4y[4] = { 0,1,0,-1 };
const ll m8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const ll m8y[8] = { 0,1,1,1,0,-1,-1,-1 };
const ll m9x[9] = { 1,1,0,-1,-1,-1,0,1,0 };
const ll m9y[9] = { 0,1,1,1,0,-1,-1,-1,0 };
struct edge {
ll from, to, cost;
bool operator<(const edge& right) const {
return cost < right.cost;
}
bool operator>(const edge& right) const {
return cost > right.cost;
}
};
struct point {
ll x, y, idx;
bool operator<(const point& right) const {
return x == right.x ? y < right.y : x < right.x;
}
bool operator>(const point& right) const {
return x == right.x ? y > right.y : x > right.x;
}
};
ll bisect_left(ll arr[], ll arr_size, ll key) {
return distance(arr, lower_bound(arr, arr + arr_size, key));
}
ll bisect_left(vector<ll> vc, ll key) {
return lower_bound(vc.begin(), vc.end(), key) - vc.begin();
}
ll pow_mod(ll a, ll x) {
if (x == 0) return 1;
if (x == 1) return a % MOD;
ll ret = pow_mod(a, x / 2);
if (x % 2 == 0) ret = (ret*ret) % MOD;
else ret = ((a % MOD) * ((ret*ret) % MOD)) % MOD;
return ret;
}
void build_mod_fact(ll arr[], ll n) {
arr[0] = 1;
repi(i, 1, n + 1) {
arr[i] = (arr[i - 1] * i) % MOD;
}
return;
}
void build_mod_fact_inv(ll arr_fact[], ll arr_fact_inv[], ll n) {
arr_fact_inv[n] = pow_mod(arr_fact[n], MOD - 2);
repd(i, n - 1, -1) {
arr_fact_inv[i] = (arr_fact_inv[i + 1] * (i + 1)) % MOD;
}
return;
}
ll comb_mod(ll n, ll r, ll arr_fact[], ll arr_fact_inv[]) {
return (((arr_fact[n] * arr_fact_inv[n - r]) % MOD) * arr_fact_inv[r]) % MOD;
}
ll gcd(ll x, ll y) {
if (y == 0) return x;
return gcd(y, x%y);
}
///////////////////////////////////////////////////////////////////////////////////////
ll n, m, s, t;
vector<edge> nodes[1010];
bool visited[1010];
priority_queue<edge, vector<edge>, greater<edge>> pq;
ll dp[2][1010];
void dijkstra(ll i, ll s, ll t) {
repi(j, 1, n + 1) {
visited[j] = false;
dp[i][j] = MAX_10p18;
}
visited[s] = true, dp[i][s] = 0;
ll cnt = 1;
repi(j, 0, nodes[s].size()) {
edge e = nodes[s][j];
pq.push(e);
}
while (true) {
if (pq.size() == 0 || cnt == n) return;
edge cur = pq.top(); pq.pop();
if (visited[cur.to]) continue;
visited[cur.to] = true;
dp[i][cur.to] = cur.cost;
cnt += 1;
repi(j, 0, nodes[cur.to].size()) {
if (visited[nodes[cur.to][j].to]) continue;
edge nxt;
nxt.to = nodes[cur.to][j].to;
nxt.cost = cur.cost + nodes[cur.to][j].cost;
pq.push(nxt);
}
}
}
ll solv() {
dijkstra(0, s, t);
dijkstra(1, t, s);
repi(i, 1, n + 1) {
if (dp[0][i] == dp[1][i] && dp[0][i] != MAX_10p18) return i;
}
return -1;
}
int main() {
cin >> n >> m;
cin >> s >> t;
repi(i, 0, m) {
ll x, y, d;
cin >> x >> y >> d;
edge e; e.to = y, e.cost = d;
nodes[x].push_back(e);
edge f; f.to = x, f.cost = d;
nodes[y].push_back(f);
}
wrln(solv());
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 身体バランス |
User |
at_cacao_jp |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3856 Byte |
Status |
AC |
Exec Time |
11 ms |
Memory |
1928 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00-sample-00, 00-sample-01, corner-case-01, corner-case-02, corner-case-03, largest-00, largest-01, largest-02, largest-03, largest-04, largest-05, random-00-0934, random-01-0457, random-02-0288, random-03-0873, random-04-0364, random-05-0053, random-06-0613, random-07-0729, random-08-0061, random-09-0645, random-10-0095, random-11-0369, random-12-0115, random-13-0260, random-14-0033, random-15-0579, random-16-0713, random-17-0336, random-18-0297, random-19-0826, random-20-0742, random-21-0264, random-22-0507, random-23-0502, random-24-0750, random-25-0721, random-26-0043, random-27-0348, random-28-0756, random-29-0647, random-30-0854, random-31-0554, random-32-0632, random-33-0776, random-34-0165, random-35-0695, random-36-0136, random-37-0831, random-38-0284, random-39-0610, random-40-0421, sample-00, sample-01 |
Case Name |
Status |
Exec Time |
Memory |
00-sample-00 |
AC |
1 ms |
256 KB |
00-sample-01 |
AC |
1 ms |
256 KB |
corner-case-01 |
AC |
1 ms |
256 KB |
corner-case-02 |
AC |
2 ms |
384 KB |
corner-case-03 |
AC |
2 ms |
384 KB |
largest-00 |
AC |
10 ms |
1472 KB |
largest-01 |
AC |
9 ms |
1472 KB |
largest-02 |
AC |
9 ms |
1476 KB |
largest-03 |
AC |
10 ms |
1472 KB |
largest-04 |
AC |
10 ms |
1532 KB |
largest-05 |
AC |
9 ms |
1472 KB |
random-00-0934 |
AC |
10 ms |
1472 KB |
random-01-0457 |
AC |
10 ms |
1920 KB |
random-02-0288 |
AC |
9 ms |
1916 KB |
random-03-0873 |
AC |
11 ms |
1472 KB |
random-04-0364 |
AC |
10 ms |
1916 KB |
random-05-0053 |
AC |
2 ms |
384 KB |
random-06-0613 |
AC |
10 ms |
1600 KB |
random-07-0729 |
AC |
10 ms |
1600 KB |
random-08-0061 |
AC |
2 ms |
512 KB |
random-09-0645 |
AC |
9 ms |
1604 KB |
random-10-0095 |
AC |
1 ms |
384 KB |
random-11-0369 |
AC |
4 ms |
896 KB |
random-12-0115 |
AC |
2 ms |
384 KB |
random-13-0260 |
AC |
5 ms |
964 KB |
random-14-0033 |
AC |
1 ms |
256 KB |
random-15-0579 |
AC |
3 ms |
512 KB |
random-16-0713 |
AC |
10 ms |
1600 KB |
random-17-0336 |
AC |
9 ms |
1920 KB |
random-18-0297 |
AC |
9 ms |
1920 KB |
random-19-0826 |
AC |
10 ms |
1604 KB |
random-20-0742 |
AC |
10 ms |
1604 KB |
random-21-0264 |
AC |
9 ms |
1920 KB |
random-22-0507 |
AC |
9 ms |
1920 KB |
random-23-0502 |
AC |
10 ms |
1920 KB |
random-24-0750 |
AC |
10 ms |
1600 KB |
random-25-0721 |
AC |
10 ms |
1604 KB |
random-26-0043 |
AC |
2 ms |
384 KB |
random-27-0348 |
AC |
10 ms |
1916 KB |
random-28-0756 |
AC |
10 ms |
1600 KB |
random-29-0647 |
AC |
10 ms |
1600 KB |
random-30-0854 |
AC |
10 ms |
1472 KB |
random-31-0554 |
AC |
9 ms |
1920 KB |
random-32-0632 |
AC |
7 ms |
1344 KB |
random-33-0776 |
AC |
10 ms |
1604 KB |
random-34-0165 |
AC |
9 ms |
1928 KB |
random-35-0695 |
AC |
4 ms |
640 KB |
random-36-0136 |
AC |
6 ms |
1224 KB |
random-37-0831 |
AC |
10 ms |
1600 KB |
random-38-0284 |
AC |
9 ms |
1924 KB |
random-39-0610 |
AC |
10 ms |
1604 KB |
random-40-0421 |
AC |
9 ms |
1920 KB |
sample-00 |
AC |
1 ms |
256 KB |
sample-01 |
AC |
1 ms |
256 KB |