Submission #3236223
Source Code Expand
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VB;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define endl "\n"
const LD EPS=1e-10;
const long long INFLL=(LL)(1e9)*(LL)(1e9);
const int INF=1e9+7;
template<class T>
void chmin(T& a, const T b)
{
if(a>b)
a=b;
}
template<class T>
void chmax(T& a, const T b)
{
if(a<b)
a=b;
}
const LL powLL(const LL p, const LL q)
{
LL t=1;
for(int i=0;i<q;i++)
t*=p;
return t;
}
template <typename T>
struct has_iter
{
private:
template <typename U>
static constexpr true_type check(typename U::iterator*);
template <typename U>
static constexpr false_type check(...);
public:
static constexpr bool value = decltype(check<T>(nullptr))::value;
};
template<typename T, typename U = typename T::iterator>
void print(const T& container)
{
auto&& first=begin(container), last=end(container);
auto&& back=prev(last);
for(auto e=first; e!=last; e=next(e))
cout<<*e<<" \n"[e==back];
}
extern void* enabler;
template<typename Head, typename enable_if<!has_iter<Head>::value>::type*& = enabler>
void print(const Head& head)
{
cout<<head<<endl;
}
template<> void print<string>(const string& container)
{
cout<<container<<endl;
}
template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
cout<<head<<" ";
print(tail...);
}
void io_speedup()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec)
{
for(T& x: vec) is >> x;
return is;
}
template<typename T, typename U>
ostream& operator << (ostream& os, const pair<T, U>& p)
{
os<<'('<<p.first<<", "<<p.second<<')';
return os;
}
template<typename T>
vector<T> read(int n)
{
vector<T> t(n);
cin>>t;
return t;
}
template<typename T>
T read()
{
T t;
cin>>t;
return t;
}
template<typename Head, typename... Tail>
struct vector_demensions
{
using type=vector<typename vector_demensions<Tail...>::type>;
};
template<typename Head>
struct vector_demensions<Head> { using type=Head; };
template<typename T>
vector<T> make_vectors(int size, T val)
{
return vector<T>(size, val);
}
template<typename T=int, typename... Args>
auto make_vectors(int size, Args... tail)
-> typename vector_demensions<Args..., T>::type
{
auto val=make_vectors<T>(forward<Args>(tail)...);
return vector<decltype(val)>(size, val);
}
typedef int Dist;
struct Edge;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
struct Edge
{
int to;
Dist dist;
Edge(int to_,Dist dist_):to(to_),dist(dist_)
{}
bool operator >(const Edge &ed)const
{
return dist > ed.dist;
}
};
//Shortest cost from i to j.
vector<Dist> dijkstra(int i, const Graph &vertex, vector<int> &preVector)
{
vector<int> pVector(vertex.size(), INF);
vector<Dist> shortest(vertex.size(), INF);
priority_queue<Edge, vector<Edge>, greater<Edge> > que;
que.push(Edge(i, 0));
shortest[i]=0;
Edge state(0,0), tmp(0,0), e(0,0);
while(!que.empty())
{
state = que.top();
que.pop();
if(shortest[state.to] < state.dist) continue;
for(Edge e : vertex[state.to])
{
if(shortest[e.to] > shortest[state.to] + e.dist)
{
shortest[e.to] = shortest[state.to] + e.dist;
pVector[e.to] = state.to;
tmp = Edge(e.to, shortest[e.to]);
que.push(tmp);
}
}
}
preVector = pVector;
return shortest;
}
vector<int> get_path(int i, int j, const vector<int> &preVector)
{
vector<int> rev;
rev.push_back(j);
int p=j;
while(p!=i)
{
p = preVector[p];
rev.push_back(p);
if(p==INF)
return vector<int>();
}
reverse(rev.begin(),rev.end());
return rev;
}
vector<Dist> dijkstra(int i, const Graph &vertex)
{
vector<int> preVector(vertex.size());
return dijkstra(i, vertex, preVector);
}
Dist dijkstra(int i,int j, const Graph &vertex)
{
return dijkstra(i, vertex)[j];
}
Dist dijkstra(int i,int j, const Graph &vertex, vector<int> &path)
{
vector<int> preVector(vertex.size());
vector<Dist> shortest(dijkstra(i, vertex, preVector));
path = get_path(i, j, preVector);
return shortest[j];
}
int main()
{
int n,m;
cin>>n>>m;
int s,t;
cin>>s>>t;
s--;
t--;
Graph g(n);
REP(i,m)
{
int x,y,d;
cin>>x>>y>>d;
x--;y--;
g[x].push_back(Edge(y,d));
g[y].push_back(Edge(x,d));
}
REP(i,n)
{
auto p=dijkstra(s,i,g);
auto q=dijkstra(i,t,g);
if(p==q)
{
print(i+1);
return 0;
}
}
print(-1);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 身体バランス |
User |
suginamiku |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5177 Byte |
Status |
WA |
Exec Time |
495 ms |
Memory |
512 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
WA |
1 ms |
256 KB |
corner-case-02 |
WA |
2 ms |
256 KB |
corner-case-03 |
WA |
2 ms |
384 KB |
largest-00 |
AC |
110 ms |
512 KB |
largest-01 |
AC |
8 ms |
512 KB |
largest-02 |
AC |
9 ms |
512 KB |
largest-03 |
AC |
10 ms |
512 KB |
largest-04 |
AC |
495 ms |
512 KB |
largest-05 |
AC |
8 ms |
512 KB |
random-00-0934 |
AC |
22 ms |
512 KB |
random-01-0457 |
AC |
9 ms |
512 KB |
random-02-0288 |
AC |
9 ms |
512 KB |
random-03-0873 |
AC |
403 ms |
512 KB |
random-04-0364 |
AC |
25 ms |
512 KB |
random-05-0053 |
AC |
2 ms |
256 KB |
random-06-0613 |
AC |
38 ms |
512 KB |
random-07-0729 |
AC |
160 ms |
512 KB |
random-08-0061 |
AC |
4 ms |
256 KB |
random-09-0645 |
AC |
8 ms |
512 KB |
random-10-0095 |
AC |
3 ms |
256 KB |
random-11-0369 |
AC |
66 ms |
384 KB |
random-12-0115 |
AC |
5 ms |
256 KB |
random-13-0260 |
AC |
30 ms |
384 KB |
random-14-0033 |
AC |
2 ms |
256 KB |
random-15-0579 |
WA |
6 ms |
384 KB |
random-16-0713 |
AC |
114 ms |
512 KB |
random-17-0336 |
AC |
18 ms |
512 KB |
random-18-0297 |
AC |
12 ms |
512 KB |
random-19-0826 |
AC |
348 ms |
512 KB |
random-20-0742 |
AC |
81 ms |
512 KB |
random-21-0264 |
AC |
26 ms |
512 KB |
random-22-0507 |
AC |
70 ms |
512 KB |
random-23-0502 |
AC |
22 ms |
512 KB |
random-24-0750 |
AC |
24 ms |
512 KB |
random-25-0721 |
AC |
21 ms |
512 KB |
random-26-0043 |
AC |
2 ms |
256 KB |
random-27-0348 |
AC |
16 ms |
512 KB |
random-28-0756 |
AC |
180 ms |
512 KB |
random-29-0647 |
AC |
248 ms |
512 KB |
random-30-0854 |
AC |
56 ms |
512 KB |
random-31-0554 |
AC |
72 ms |
512 KB |
random-32-0632 |
AC |
41 ms |
512 KB |
random-33-0776 |
AC |
55 ms |
512 KB |
random-34-0165 |
AC |
25 ms |
512 KB |
random-35-0695 |
AC |
5 ms |
384 KB |
random-36-0136 |
AC |
12 ms |
384 KB |
random-37-0831 |
AC |
149 ms |
512 KB |
random-38-0284 |
AC |
22 ms |
512 KB |
random-39-0610 |
AC |
64 ms |
512 KB |
random-40-0421 |
AC |
24 ms |
512 KB |
sample-00 |
AC |
1 ms |
256 KB |
sample-01 |
AC |
1 ms |
256 KB |