Submission #3603042
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define countof(a) (sizeof(a)/sizeof(*a))
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()
#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to) for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to) UPTO(var, 0, (to)-1)
#define DOWN(var, from) DOWNTO(var, (from)-1, 0)
#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--
#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)
#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;
struct Comb {
vector<vector<s64> > data;
Comb(int n) { // O(n^2)
data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
UPTO(i,1,n) {
FOR(j,i+1) {
if (!j || j == i) data[i][j] = 1;
else data[i][j] = data[i-1][j-1] + data[i-1][j];
}
}
}
s64 ncr(int n, int r) {
return data[n][r];
}
};
static inline int ri() {
int a;
scanf("%d", &a);
return a;
}
int int_less(const void *a, const void *b) {
return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
return (*((const int*)b) - *((const int*)a));
}
struct Graph {
int n;
vector<vector<pair<int, s64> > > hen;
// result of Bellman–Ford
vector<vector<s64> > BF;
set<int> bf_completed;
Graph(int n) { // O(N)
hen.resize(n, vector<pair<int, s64> >());
BF.resize(n, vector<s64>());
this->n = n;
}
int spfa(int k) {
vector<bool> inque(n,false);
vector<int> updated(n,0);
bf_completed.insert(k);
BF[k].resize(n,LINF);
BF[k][k] = 0;
queue<int> que;
inque[k] = true;
que.push(k);
updated[k]++;
while (que.size()) {
int i = que.front(); que.pop();
int n_hen = hen[i].size();
FOR(j,n_hen) {
if (BF[k][hen[i][j].fi] > BF[k][i] + hen[i][j].se) {
BF[k][hen[i][j].fi] = BF[k][i] + hen[i][j].se;
if (!inque[hen[i][j].fi]) {
inque[hen[i][j].fi] = true;
que.push(hen[i][j].fi);
}
}
}
inque[i] = false;
}
return -1;
}
s64 shortest(int from, int to) {
return BF[from][to];
}
void add_hen(int from, int to, s64 cost, bool muki) {
hen[from].push_back(mp(to, cost));
if (!muki) hen[to].push_back(mp(from, cost));
}
};
// Graph.dfs : O(N)
// Graph.dij : O(N+MlogM)
// Graph.bf : O(NM)
// Graph.wf : O(N^3)
// Graph.reachable
// Graph.shortest
int hen0_to[100000];
int hen0_cost[100000];
int hen0;
int hen1_to[100000];
int hen1_cost[100000];
int hen1;
int main() {
int n = ri();
int m = ri();
int s = ri()-1;
int t = ri()-1;
Graph yen(n);
Graph snuke(n);
FOR(i,m) {
int a = ri()-1;
int b = ri()-1;
yen.add_hen(a,b,ri(),false);
snuke.add_hen(a,b,ri(),false);
}
yen.spfa(s);
snuke.spfa(t);
s64 cost[n];
FOR(i,n) {
cost[i] = yen.shortest(s,i) + snuke.shortest(t,i);
}
s64 mini[n];
DOWN(i,n) {
if (i == n-1) mini[i] = cost[i];
else mini[i] = min(mini[i+1], cost[i]);
}
FOR(i,n) {
cout << 1000000000000000LL-mini[i] << endl;
}
return 0;
}
Submission Info
Submission Time
2018-11-15 17:25:13+0900
Task
D - Saving Snuuk
User
QCFium
Language
C++14 (GCC 5.4.1)
Score
400
Code Size
3988 Byte
Status
AC
Exec Time
331 ms
Memory
24704 KB
Compile Error
./Main.cpp: In function ‘int ri()’:
./Main.cpp:62:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
400 / 400
Status
Set Name
Test Cases
Sample
sampleRnd.txt, sampleT.txt
All
00yorimichi.txt, 11_0.txt, 11_1.txt, 11_2.txt, 11_3.txt, 11_4.txt, 1n1m1.txt, 1oo_0.txt, 1oo_1.txt, 1oo_2.txt, 1oo_3.txt, 1oo_4.txt, dangou_0.txt, dangou_1.txt, dangou_2.txt, dangou_3.txt, dangou_4.txt, edge.txt, high_0.txt, high_1.txt, high_2.txt, high_3.txt, high_4.txt, low_0.txt, low_1.txt, low_2.txt, low_3.txt, low_4.txt, oo1_0.txt, oo1_1.txt, oo1_2.txt, oo1_3.txt, oo1_4.txt, path_0.txt, path_1.txt, path_2.txt, path_3.txt, path_4.txt, path_5.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sampleRnd.txt, sampleT.txt, slast_0.txt, slast_1.txt, slast_2.txt, slast_3.txt, slast_4.txt, tlast_0.txt, tlast_1.txt, tlast_2.txt, tlast_3.txt, tlast_4.txt
Case Name
Status
Exec Time
Memory
00yorimichi.txt
AC
233 ms
24056 KB
11_0.txt
AC
247 ms
19220 KB
11_1.txt
AC
86 ms
11776 KB
11_2.txt
AC
131 ms
12920 KB
11_3.txt
AC
299 ms
24452 KB
11_4.txt
AC
274 ms
21092 KB
1n1m1.txt
AC
185 ms
15960 KB
1oo_0.txt
AC
219 ms
18344 KB
1oo_1.txt
AC
231 ms
19220 KB
1oo_2.txt
AC
54 ms
8704 KB
1oo_3.txt
AC
245 ms
20092 KB
1oo_4.txt
AC
223 ms
19220 KB
dangou_0.txt
AC
52 ms
9216 KB
dangou_1.txt
AC
147 ms
12984 KB
dangou_2.txt
AC
275 ms
19932 KB
dangou_3.txt
AC
45 ms
6272 KB
dangou_4.txt
AC
331 ms
24704 KB
edge.txt
AC
316 ms
24696 KB
high_0.txt
AC
72 ms
7936 KB
high_1.txt
AC
90 ms
10240 KB
high_2.txt
AC
290 ms
22960 KB
high_3.txt
AC
9 ms
1664 KB
high_4.txt
AC
227 ms
18024 KB
low_0.txt
AC
63 ms
11008 KB
low_1.txt
AC
65 ms
9344 KB
low_2.txt
AC
255 ms
20944 KB
low_3.txt
AC
220 ms
19420 KB
low_4.txt
AC
139 ms
13416 KB
oo1_0.txt
AC
249 ms
21340 KB
oo1_1.txt
AC
191 ms
17100 KB
oo1_2.txt
AC
147 ms
14232 KB
oo1_3.txt
AC
94 ms
11904 KB
oo1_4.txt
AC
135 ms
13992 KB
path_0.txt
AC
262 ms
21168 KB
path_1.txt
AC
258 ms
21168 KB
path_2.txt
AC
119 ms
10460 KB
path_3.txt
AC
157 ms
13104 KB
path_4.txt
AC
80 ms
7296 KB
path_5.txt
AC
232 ms
18524 KB
rnd_0.txt
AC
233 ms
18972 KB
rnd_1.txt
AC
319 ms
23336 KB
rnd_2.txt
AC
17 ms
2432 KB
rnd_3.txt
AC
286 ms
21968 KB
rnd_4.txt
AC
149 ms
13264 KB
sampleRnd.txt
AC
1 ms
256 KB
sampleT.txt
AC
1 ms
256 KB
slast_0.txt
AC
234 ms
18348 KB
slast_1.txt
AC
64 ms
8192 KB
slast_2.txt
AC
286 ms
22960 KB
slast_3.txt
AC
158 ms
14216 KB
slast_4.txt
AC
250 ms
19972 KB
tlast_0.txt
AC
83 ms
10368 KB
tlast_1.txt
AC
210 ms
17228 KB
tlast_2.txt
AC
266 ms
22088 KB
tlast_3.txt
AC
304 ms
24580 KB
tlast_4.txt
AC
297 ms
24580 KB