#include <bits/stdc++.h>
using namespace std ;
const long long inf = 1e18 ;
const int MAX = 1e5 + 10 ;
int arr[MAX] ;
int n , m ;
vector< vector< array<int , 3> > >adj(MAX) ;
long long dist[MAX] ;
void dijkstra(int src)
{
for(int i = 1 ; i <= n ; ++i)
dist[i] = inf ;
priority_queue< pair<long long , int> , vector< pair<long long , int> > , greater< pair<long long , int> > >q ;
dist[src] = 0 ;
q.push({0 , src}) ;
while(!q.empty())
{
pair<long long , int>p = q.top() ;
q.pop() ;
int node = p.second ;
long long cost = p.first ;
if(dist[node] < cost)
continue ;
sort(adj[node].begin() , adj[node].end()) ;
int sz = adj[node].size() ;
for(int i = 0 ; i < sz ; ++i)
{
int child2 = adj[node][i][1] ;
long long cost2 = cost + adj[node][i][2] ;
if(cost2 < dist[child2])
{
dist[child2] = cost2 ;
q.push({cost2 , child2}) ;
}
int cnt = 0 , idx = -1 ;
if(i-1 >= 0 && adj[node][i][0] == adj[node][i-1][0])
cnt++ , idx = i-1 ;
if(i+1 < sz && adj[node][i][0] == adj[node][i+1][0])
cnt++ , idx = i+1 ;
if(i+2 < sz && adj[node][i][0] == adj[node][i+2][0])
cnt++ , idx = i+2 ;
cost2 = cost ;
if(cost2 < dist[child2] && (cnt == 0 || (cnt == 1 && dist[adj[node][idx][1]] + adj[node][idx][2] == dist[node])))
{
dist[child2] = cost2 ;
q.push({cost2 , child2}) ;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>m ;
for(int i = 0 ; i < m ; ++i)
{
int x , y , c , w ;
cin>>x>>y>>c>>w ;
adj[x].push_back({c , y , w}) ;
adj[y].push_back({c , x , w}) ;
}
dijkstra(1) ;
if(dist[n] == inf)
dist[n] = -1 ;
return cout<<dist[n]<<"\n" , 0 ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
3 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
8164 KB |
Output is correct |
2 |
Correct |
17 ms |
5204 KB |
Output is correct |
3 |
Correct |
52 ms |
11020 KB |
Output is correct |
4 |
Correct |
25 ms |
6292 KB |
Output is correct |
5 |
Correct |
125 ms |
15848 KB |
Output is correct |
6 |
Correct |
104 ms |
16036 KB |
Output is correct |
7 |
Correct |
103 ms |
15900 KB |
Output is correct |
8 |
Incorrect |
92 ms |
15568 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
3 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |