Submission #618037
Source Code Expand
#include <bits/stdc++.h>
#include <alloca.h>
using namespace std;
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
string itos(long long n){
stringstream ss;
ss << n;
return ss.str();
}
template<class T> ostream& operator<<(ostream& os, const pair<T,T>& p)
{
os << "(" << p.first << "," << p.second << ")";
return os;
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& arr)
{
os << "{";
for(int i = 0 ; i < arr.size() ; i++) os << (i==0?"":",") << arr[i];
os << "}";
return os;
}
template<class T,int X> ostream& operator<<(ostream& os, const array<T,X> & arr)
{
os << "{";
for(int i = 0 ; i < arr.size() ; i++) os << (i==0?"":",") << arr[i];
os << "}";
return os;
}
#define int long long
struct Node{
int a,b,c1,c2,c3;
};
vector<Node> g[30000];
vector<Node> rg[30000];
bool operator < (const Node &a,const Node &b){
return a.c1 > b.c1;
}
// > w[j], w[j] += w[j-1];
// for(int j = 1 ; j < L ; j++){
// g[id[j-1]].push_back({id[j-1],id[j],w[j]-w[j-1],2*(w[L-1]-w[j])});
// g[id[j]].push_back({id[j],id[j-1],w[j]-w[j-1],2*w[j-1]});
// }
int sd[30000];
signed main(){
for(int i = 0 ; i < 30000 ; i++)
sd[i] = 1e18;
int N,M,src,dst;
cin >> N >> M >> src >> dst;
for(int i = 0 ; i < M ; i++){
int L;
cin >> L;
vector<int> id(L);
vector<int> w(L);
for(int j = 0 ; j < L ; j++) cin >> id[j];
int tot = 0;
w[0] = 0;
for(int j = 1 ; j < L ; j++) cin >> w[j], w[j] += w[j-1];
for(int j = 1 ; j < L ; j++){
g[id[j-1]].push_back({id[j-1],id[j],w[j]-w[j-1],id[L-1],w[L-1]-w[j]});
g[id[j]].push_back({id[j],id[j-1],w[j]-w[j-1],id[0],w[j-1]});
}
}
for(int i = 0 ; i < N ; i++){
for( auto e : g[i] ){
swap(e.a,e.b);
rg[e.a].push_back(e);
}
}
{
map<int,int> cost[30000];
priority_queue<Node> Q;
Q.push({dst,-1,0,0});
while( Q.size() ){
Node q = Q.top(); Q.pop();
if( cost[q.a][q.c2] != q.c1 ) continue;
sd[q.a] = q.c1;
for( auto e : rg[q.a] ){
Node nq = {e.b,-1,q.c1+e.c1,0};
if( cost[nq.a].count(nq.c2) == 0 || cost[nq.a][nq.c2] > nq.c1 ){
cost[nq.a][nq.c2]= nq.c1;
Q.push(nq);
}
}
}
}
{
map<int,int> cost[30000];
priority_queue<Node> Q;
Q.push({src,-1,0,0});
int ans = 1e9;
while( Q.size() ){
Node q = Q.top(); Q.pop();
if( cost[q.a][q.c2] != q.c1 ) continue;
if( q.a == dst ){
ans = min(max(q.c1,q.c2),ans);
continue;
}
for( auto e : g[q.a] ){
Node nq = {e.b,-1,q.c1+e.c1,max(q.c2,sd[e.c2] + e.c1 + e.c3 + q.c1)};
if( cost[nq.a].size() ){
auto it = cost[nq.a].upper_bound(nq.c2);
if( it != cost[nq.a].begin() ){
--it;
if( it->second <= nq.c1 ) continue;
}
}
if( cost[nq.a].count(nq.c2) == 0 || cost[nq.a][nq.c2] > nq.c1 ){
cost[nq.a][nq.c2]= nq.c1;
Q.push(nq);
}
}
}
cout << ans << endl;
}
}
Submission Info
Submission Time |
|
Task |
C - メンテナンス明け |
User |
kyuridenamida |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
2989 Byte |
Status |
AC |
Exec Time |
898 ms |
Memory |
36740 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 |
large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name |
Status |
Exec Time |
Memory |
large/20_large-00 |
AC |
898 ms |
36740 KB |
large/20_large-01 |
AC |
540 ms |
28948 KB |
large/20_large-02 |
AC |
198 ms |
16788 KB |
large/20_large-03 |
AC |
323 ms |
23448 KB |
large/20_large-04 |
AC |
463 ms |
27408 KB |
large/31_max_large |
AC |
80 ms |
10136 KB |
small/00_sample00 |
AC |
31 ms |
3740 KB |
small/00_sample01 |
AC |
32 ms |
3748 KB |
small/00_sample02 |
AC |
32 ms |
3748 KB |
small/10_small-0000 |
AC |
34 ms |
4000 KB |
small/10_small-0001 |
AC |
34 ms |
3872 KB |
small/10_small-0002 |
AC |
34 ms |
4004 KB |
small/10_small-0003 |
AC |
34 ms |
4000 KB |
small/10_small-0004 |
AC |
34 ms |
4008 KB |
small/10_small-0005 |
AC |
36 ms |
4120 KB |
small/10_small-0006 |
AC |
35 ms |
4000 KB |
small/10_small-0007 |
AC |
32 ms |
3992 KB |
small/10_small-0008 |
AC |
32 ms |
3868 KB |
small/10_small-0009 |
AC |
30 ms |
3876 KB |
small/10_small-0010 |
AC |
29 ms |
4004 KB |
small/10_small-0011 |
AC |
32 ms |
4000 KB |
small/10_small-0012 |
AC |
32 ms |
3988 KB |
small/10_small-0013 |
AC |
30 ms |
4120 KB |
small/10_small-0014 |
AC |
30 ms |
4004 KB |
small/10_small-0015 |
AC |
34 ms |
4020 KB |
small/10_small-0016 |
AC |
33 ms |
3996 KB |
small/10_small-0017 |
AC |
34 ms |
3892 KB |
small/10_small-0018 |
AC |
31 ms |
3868 KB |
small/10_small-0019 |
AC |
32 ms |
3992 KB |
small/30_max_small |
AC |
31 ms |
3880 KB |
small/40_simple_0000 |
AC |
30 ms |
3748 KB |
small/40_simple_0001 |
AC |
29 ms |
3756 KB |
small/40_simple_0002 |
AC |
30 ms |
3752 KB |
small/40_simple_0003 |
AC |
32 ms |
3800 KB |
small/40_simple_0004 |
AC |
29 ms |
3828 KB |
small/40_simple_0005 |
AC |
32 ms |
3740 KB |
small/40_simple_0006 |
AC |
29 ms |
3744 KB |
small/40_simple_0007 |
AC |
31 ms |
3744 KB |
small/40_simple_0008 |
AC |
29 ms |
3752 KB |
small/40_simple_0009 |
AC |
32 ms |
3740 KB |
small/40_simple_0010 |
AC |
32 ms |
3756 KB |
small/40_simple_0011 |
AC |
32 ms |
3744 KB |
small/40_simple_0012 |
AC |
32 ms |
3744 KB |
small/40_simple_0013 |
AC |
30 ms |
3748 KB |
small/40_simple_0014 |
AC |
34 ms |
3752 KB |
small/40_simple_0015 |
AC |
32 ms |
3752 KB |
small/40_simple_0016 |
AC |
35 ms |
3824 KB |
small/40_simple_0017 |
AC |
33 ms |
3744 KB |
small/40_simple_0018 |
AC |
32 ms |
3756 KB |
small/40_simple_0019 |
AC |
34 ms |
3748 KB |
small/90_dijkstra_killer_00 |
AC |
34 ms |
3864 KB |
small/90_dijkstra_killer_01 |
AC |
31 ms |
3864 KB |
small/91_tayama_killer_00 |
AC |
32 ms |
3744 KB |
small/91_tayama_killer_01 |
AC |
32 ms |
3744 KB |
small/91_tayama_killer_02 |
AC |
33 ms |
3864 KB |
small/91_tayama_killer_03 |
AC |
32 ms |
3748 KB |
small/91_tayama_killer_04 |
AC |
31 ms |
3744 KB |
small/91_tayama_killer_05 |
AC |
32 ms |
3748 KB |