#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
struct gujo
{
ll U, V, C, D;
};
ll n, m;
vector<pll> vec[210], yuk[210];
vector< pair<ll, pll> > vec2[210];
gujo tmp;
ll Jdist[210][210][2];
ll Ydist[210][210][2];
multiset<pll> Jst[210][2], Yst[210][2];
ll ans = INF;
void dijksta1(ll X)
{
priority_queue<pll> pq;
for(ll i = 1 ; i <= n ; i++)
Jdist[X][i][0] = Jdist[X][i][1] = INF;
Jdist[X][1][0] = 0;
pq.push({0, 1});
while(!pq.empty())
{
pll qq = pq.top();
pq.pop();
for(auto &i : vec[qq.se])
{
if(i.fi == X)
continue;
if(Jdist[X][i.fi][0] > Jdist[X][qq.se][0] + i.se)
{
Jdist[X][i.fi][0] = Jdist[X][qq.se][0] + i.se;
pq.push({-Jdist[X][i.fi][0], i.fi});
}
}
}
Jdist[X][n][1] = 0;
pq.push({0, n});
while(!pq.empty())
{
pll qq = pq.top();
pq.pop();
for(auto &i : vec[qq.se])
{
if(i.fi == X)
continue;
if(Jdist[X][i.fi][1] > Jdist[X][qq.se][1] + i.se)
{
Jdist[X][i.fi][1] = Jdist[X][qq.se][1] + i.se;
pq.push({-Jdist[X][i.fi][1], i.fi});
}
}
}
}
void dijksta2(ll X)
{
priority_queue<pll> pq;
for(ll i = 1 ; i <= n ; i++)
Ydist[X][i][0] = Ydist[X][i][1] = INF;
Ydist[X][1][0] = 0;
pq.push({0, 1});
while(!pq.empty())
{
pll qq = pq.top();
pq.pop();
for(auto &i : yuk[qq.se])
{
if(i.fi == X)
continue;
if(Ydist[X][i.fi][0] > Ydist[X][qq.se][0] + i.se)
{
Ydist[X][i.fi][0] = Ydist[X][qq.se][0] + i.se;
pq.push({-Ydist[X][i.fi][0], i.fi});
}
}
}
Ydist[X][n][1] = 0;
pq.push({0, n});
while(!pq.empty())
{
pll qq = pq.top();
pq.pop();
for(auto &i : yuk[qq.se])
{
if(i.fi == X)
continue;
if(Ydist[X][i.fi][1] > Ydist[X][qq.se][1] + i.se)
{
Ydist[X][i.fi][1] = Ydist[X][qq.se][1] + i.se;
pq.push({-Ydist[X][i.fi][1], i.fi});
}
}
}
}
int main(void)
{
fastio
cin >> n >> m;
for(ll i = 1 ; i <= m ; i++)
{
cin >> tmp.U >> tmp.V >> tmp.C >> tmp.D;
vec[tmp.U].push_back({tmp.V, tmp.C});
yuk[tmp.V].push_back({tmp.U, tmp.C});
vec2[tmp.U].push_back({tmp.V, {tmp.C, tmp.D}});
}
dijksta1(0);
dijksta2(0);
for(ll i = 2 ; i < n ; i++)
{
dijksta1(i);
dijksta2(i);
}
ans = min(ans, Jdist[0][n][0] + Jdist[0][1][1]);
for(ll i = 1 ; i <= n ; i++)
{
for(auto &j : yuk[i])
{
Jst[i][0].insert({Jdist[0][j.fi][0] + j.se, j.fi});
Jst[i][1].insert({Jdist[0][j.fi][1] + j.se, j.fi});
}
for(auto &j : vec[i])
{
Yst[i][0].insert({Ydist[0][j.fi][0] + j.se, j.fi});
Yst[i][1].insert({Ydist[0][j.fi][1] + j.se, j.fi});
}
}
for(ll i = 1 ; i <= n ; i++)
{
for(auto &j : vec2[i]) //i -> j
{
ll cost1 = INF, cost2 = INF;
for(auto &k : vec2[i])
{
if(j == k)
continue;
cost1 = min(cost1, Jdist[0][i][0] + k.se.fi + Ydist[0][k.fi][1]);
}
if(i != 1 && i != n)
cost1 = min(cost1, Jdist[i][n][0]);
auto p1 = Jst[j.fi][0].begin();
auto p2 = Yst[i][1].begin();
if((*p1).se == i)
{
p1++;
if(p1 != Jst[j.fi][0].end() && (*p1).se == i)
p1--;
}
if((*p2).se == j.fi)
{
p2++;
if(p2 != Yst[i][1].end() && (*p2).se == i)
p2--;
}
if(p1 != Jst[j.fi][0].end() && p2 != Yst[i][1].end())
cost1 = min(cost1, (*p1).fi + j.se.fi + (*p2).fi);
if(i == n)
cost1 = min(cost1, j.se.fi + (*p1).fi);
if(j.fi == 1)
cost1 = min(cost1, j.se.fi + (*p2).fi);
if(i == n && j.fi == 1)
cost1 = min(cost1, j.se.fi);
for(auto &k : vec2[i])
{
if(j == k)
continue;
cost2 = min(cost2, Jdist[0][i][1] + k.se.fi + Ydist[0][k.fi][0]);
}
if(i != 1 && i != n)
cost2 = min(cost2, Jdist[i][1][1]);
p1 = Jst[j.fi][1].begin();
p2 = Yst[i][0].begin();
if((*p1).se == i)
{
p1++;
if(p1 != Jst[j.fi][1].end() && (*p1).se == i)
p1--;
}
if((*p2).se == j.fi)
{
p2++;
if(p2 != Yst[i][0].end() && (*p2).se == j.fi)
p2--;
}
if(p1 != Jst[j.fi][1].end() && p2 != Yst[i][0].end())
cost2 = min(cost2, (*p1).fi + j.se.fi + (*p2).fi);
if(i == 1)
cost2 = min(cost2, j.se.fi + (*p1).fi);
if(j.fi == n)
cost2 = min(cost2, j.se.fi + (*p2).fi);
if(i == 1 && j.fi == n)
cost2 = min(cost2, j.se.fi);
ans = min(ans, cost1 + cost2 + j.se.se);
}
}
if(ans >= INF - 10000000000)
cout << -1;
else
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2004 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
19 ms |
2020 KB |
Output is correct |
4 |
Correct |
20 ms |
1956 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
1748 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
29 ms |
1940 KB |
Output is correct |
11 |
Correct |
27 ms |
1996 KB |
Output is correct |
12 |
Incorrect |
27 ms |
1952 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
323 ms |
17952 KB |
Output is correct |
2 |
Correct |
317 ms |
18120 KB |
Output is correct |
3 |
Correct |
320 ms |
19232 KB |
Output is correct |
4 |
Correct |
22 ms |
2308 KB |
Output is correct |
5 |
Correct |
11 ms |
2008 KB |
Output is correct |
6 |
Correct |
3 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
0 ms |
388 KB |
Output is correct |
9 |
Correct |
161 ms |
19428 KB |
Output is correct |
10 |
Correct |
156 ms |
19580 KB |
Output is correct |
11 |
Correct |
260 ms |
19108 KB |
Output is correct |
12 |
Correct |
258 ms |
19116 KB |
Output is correct |
13 |
Correct |
267 ms |
19252 KB |
Output is correct |
14 |
Correct |
262 ms |
19532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1972 KB |
Output is correct |
2 |
Incorrect |
2 ms |
1748 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2004 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
19 ms |
2020 KB |
Output is correct |
4 |
Correct |
20 ms |
1956 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
1748 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
29 ms |
1940 KB |
Output is correct |
11 |
Correct |
27 ms |
1996 KB |
Output is correct |
12 |
Incorrect |
27 ms |
1952 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |