#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
signed main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int nbSommets, nbAretes;
cin >> nbSommets >> nbAretes;
vector<vector<tuple<int, int, int>>> aretesAdj(nbSommets+1);
for (int iArete = 0; iArete < nbAretes; ++iArete)
{
int u, v, iCol, cost;
cin >> u >> v >> iCol >> cost;
aretesAdj[u].emplace_back(iCol, v, cost);
aretesAdj[v].emplace_back(iCol, u, cost);
}
int szAdj = nbSommets;
vector<vector<pair<int, int>>> adj(nbSommets+1);
for (int iSommet = 1; iSommet <= nbSommets; ++iSommet)
{
sort(aretesAdj[iSommet].begin(), aretesAdj[iSommet].end());
int deg = aretesAdj[iSommet].size();
for (int iAdj(0); iAdj < deg;)
{
int iPos(iAdj);
int col = get<0>(aretesAdj[iSommet][iAdj]);
int totCost = 0;
while (iPos < deg and get<0>(aretesAdj[iSommet][iPos]) == col)
totCost += get<2>(aretesAdj[iSommet][iPos++]);
adj.emplace_back();
adj[iSommet].emplace_back(++szAdj, 0);
for (int i(iAdj); i < iPos; ++i)
{
auto [icol, iFrere, cost] = aretesAdj[iSommet][i];
adj[iSommet].emplace_back(iFrere, cost);
adj[iFrere].emplace_back(szAdj, 0);
adj[szAdj].emplace_back(iFrere, totCost - cost);
}
iAdj = iPos;
}
}
vector<int> dis(1+adj.size(), INF);
dis[0] = 0;
priority_queue<pair<int, int>> pq;
pq.emplace(0, 1);
while (!pq.empty())
{
auto [curDis, iNoeud] = pq.top(); pq.pop();
curDis = -curDis;
if (dis[curDis] < curDis) continue;
for (auto [iFrere, iCout] : adj[iNoeud])
if (iCout + curDis < dis[iFrere])
{
dis[iFrere] = iCout + curDis;
pq.emplace(-dis[iFrere], iFrere);
}
}
int sol = dis[nbSommets];
if (sol == INF) sol = -1;
cout<< sol << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
145 ms |
23656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Runtime error |
1 ms |
620 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |