#include <bits/stdc++.h>
#define DIMN 210
#define INF 2000000000
using namespace std;
int dp[DIMN] , dist[DIMN][DIMN];
priority_queue < pair <int , int > > h;
vector <pair <int , pair <int , int > > > v[DIMN];
struct idk{
int x , y , z , c;
} mch[50010];
char buff[5000000];
int pos , n;
int getnr(){
int nr = 0;
while ('0' > buff[pos] || buff[pos] > '9')
pos++;
while ('0' <= buff[pos] && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
int dijkstra (int which){
int i , val , nod , vecin , cost , nr;
val = 0;
for (i = 1 ; i <= n ; i++)
dp[i] = INF;
dp[1] = 0;
h.push(make_pair(0 , 1));
while (!h.empty()){
nod = h.top().second;
cost = -h.top().first;
h.pop();
if (dp[nod] != cost)
continue;
if (nod == mch[which].y){
cost = dp[nod] + mch[which].z;
if (dp[mch[which].x] > cost){
dp[mch[which].x] = cost;
h.push(make_pair(-cost , mch[which].x));
}
}
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
nr = v[nod][i].second.second;
if (nr != which){
cost = dp[nod] + mch[nr].z;
if (dp[vecin] > cost){
dp[vecin] = cost;
h.push(make_pair(-cost , vecin));
}
}
}
}
val = dp[n];
/// --------------------------------------------------------------------------
for (i = 1 ; i <= n ; i++)
dp[i] = INF;
dp[n] = 0;
h.push(make_pair(0 , n));
while (!h.empty()){
nod = h.top().second;
cost = -h.top().first;
h.pop();
if (dp[nod] != cost)
continue;
if (nod == mch[which].y){
cost = dp[nod] + mch[which].z;
if (dp[mch[which].x] > cost){
dp[mch[which].x] = cost;
h.push(make_pair(-cost , mch[which].x));
}
}
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
nr = v[nod][i].second.second;
if (nr != which){
cost = dp[nod] + mch[nr].z;
if (dp[vecin] > cost){
dp[vecin] = cost;
h.push(make_pair(-cost , vecin));
}
}
}
}
return val + dp[1];
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int m , x , y , z , c , i , j , k;
long long sol , val;
fread (buff , 1 , 5000000 , fin);
n = getnr();
m = getnr();
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= m ; j++){
dist[i][j] = INF;
}
dist[i][i] = 0;
}
for (i = 1 ; i <= m ; i++){
x = getnr();
y = getnr();
z = getnr();
c = getnr();
v[x].push_back(make_pair(y , make_pair(z , i)));
mch[i] = {x , y , z , c};
dist[x][y] = min(dist[x][y] , z);
}
for (k = 1 ; k <= n ; k++){
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= n ; j++){
if (i != j && i != k && j != k && dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
}
}
}
sol = 1LL * dist[1][n] + dist[n][1];
/// sol pt cand nu inversez nimic
/// ce fac daca aleg sa inversez ceva?
for (i = 1 ; i <= m ; i++){
/// daca as inversa muchia i as rezolva ceva?
val = min(1LL * dist[1][n] , 1LL * dist[1][mch[i].y] + dist[mch[i].x][n] + mch[i].z + mch[i].c);
val += min(1LL * dist[n][1] , 1LL * dist[n][mch[i].y] + mch[i].z + mch[i].c + dist[mch[i].x][1]);
if (val < sol){
sol = min(sol , 1LL * dijkstra (i) + mch[i].c);
}
}
if (sol >= INF)
sol = -1;
fprintf (fout,"%lld",sol);
return 0;
}
Compilation message
ho_t4.cpp: In function 'int dijkstra(int)':
ho_t4.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
ho_t4.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < v[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:154:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread (buff , 1 , 5000000 , fin);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
512 KB |
Output is correct |
| 2 |
Correct |
19 ms |
512 KB |
Output is correct |
| 3 |
Correct |
21 ms |
512 KB |
Output is correct |
| 4 |
Correct |
20 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
19 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
2816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
640 KB |
Output is correct |
| 2 |
Correct |
18 ms |
512 KB |
Output is correct |
| 3 |
Runtime error |
7 ms |
2304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
512 KB |
Output is correct |
| 2 |
Correct |
19 ms |
512 KB |
Output is correct |
| 3 |
Correct |
21 ms |
512 KB |
Output is correct |
| 4 |
Correct |
20 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
19 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
