#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const ll INF = 1e18;
const int nax = 210, mx = 50*1000+10;
int n,m;
vector<pi> V[nax];
pi edge[mx];
int inv[mx], cost[mx];
ll dist[nax];
bool done[nax];
void dijkstra(int x) {
priority_queue<pair<ll,int> > PQ;
PQ.push({0,x});
for(int i = 1; i <= n; ++i) dist[i] = INF;
dist[x] = 0;
while(!PQ.empty()) {
pair<ll,int>tp = PQ.top();
PQ.pop();
tp.ST = -tp.ST;
if(dist[tp.ND] < tp.ST) continue;
for(auto nbh : V[tp.ND]) {
if(!done[nbh.ND]) {
if(dist[nbh.ST] > tp.ST + cost[nbh.ND]) {
dist[nbh.ST] = tp.ST + cost[nbh.ND];
PQ.push({-dist[nbh.ST],nbh.ST});
}
}
}
}
}
int main() {_
cin >> n >> m;
for(int a,b,i = 1; i <= m; ++i) {
cin >> a >> b >> cost[i] >> inv[i];
edge[i] = {a,b};
V[a].PB({b,i});
}
ll ans = INF;
for(int i = 1; i <= m; ++i) {
ll c = inv[i];
int a = edge[i].ST, b = edge[i].ND;
V[b].PB({a,m+1});
cost[m+1] = cost[i];
done[i] = 1;
dijkstra(1);
c += dist[n];
//cout << inv[i] << " ";
//cout << dist[n] << " ";
dijkstra(n);
c += dist[1];
//cout << dist[1] << "\n";
done[i] = 0;
ans = min(ans,c);
V[b].pop_back();
}
if(ans == INF) cout << "-1";
else cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
40 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1094 ms |
2816 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
19 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
40 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |