#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 1;
const int oo = 1e16;
map<int,int> cc[N];
int n, m, color[N], dp[N];
struct mmb
{
int vertex, dlab, prec;
bool operator < (const mmb& other) const
{
return dlab > other.dlab;
}
};
struct tripple
{
int fi, se, th;
};
vector<tripple> adj[N];
void dijikstra()
{
dp[1] = 0;
priority_queue<mmb> Q;
Q.push({1, 0});
while(!Q.empty())
{
auto u = Q.top(); Q.pop();
// cout<<endl<<u.vertex<<" : "<<endl;
if(u.dlab != dp[u.vertex]) continue;
for(auto v : adj[u.vertex])
{
// cout << v.fi<<" - ";
if((cc[u.vertex][v.se] > 2 && u.prec == v.se) || (u.prec != v.se && cc[u.vertex][v.se] > 1))
{
// cout<<"1 : "<<dp[v.fi]<<" "<<u.dlab + v.th<<endl;
if(dp[v.fi] > u.dlab + v.th){
// cout<<"OK\n";
dp[v.fi] = u.dlab + v.th;
Q.push({v.fi, dp[v.fi], v.se});
}
}
else
{
// cout<<"2 : "<<dp[v.fi]<<" "<<u.dlab + v.th<<endl;
if(dp[v.fi] > u.dlab)
{
// cout<<"OK\n";
dp[v.fi] = u.dlab;
Q.push({v.fi, dp[v.fi], v.se});
}
}
}
}
}
int32_t main()
{
// freopen("test.inp", "r" ,stdin);
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) dp[i] = oo;
for(int i = 1; i <= m; i++)
{
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
cc[a][c]++;
cc[b][c]++;
}
dijikstra();
if(dp[n] == oo) cout<<"-1";
else cout << dp[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
74072 KB |
Output is correct |
2 |
Correct |
16 ms |
74076 KB |
Output is correct |
3 |
Correct |
16 ms |
74076 KB |
Output is correct |
4 |
Correct |
15 ms |
74076 KB |
Output is correct |
5 |
Correct |
16 ms |
74480 KB |
Output is correct |
6 |
Correct |
15 ms |
74208 KB |
Output is correct |
7 |
Incorrect |
17 ms |
74332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
85936 KB |
Output is correct |
2 |
Incorrect |
53 ms |
79684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
74072 KB |
Output is correct |
2 |
Correct |
16 ms |
74076 KB |
Output is correct |
3 |
Correct |
16 ms |
74076 KB |
Output is correct |
4 |
Correct |
15 ms |
74076 KB |
Output is correct |
5 |
Correct |
16 ms |
74480 KB |
Output is correct |
6 |
Correct |
15 ms |
74208 KB |
Output is correct |
7 |
Incorrect |
17 ms |
74332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |