#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (int)(1e8)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ld pointdist(ld x, ld y, ld point) { return ((x-point)*(y-point))/abs(x-y); }
//ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
////////////******SOLUTION******\\\\\\\\\\\
const int MAX_N = 1e5 + 4;
int n, m;
map<pii,int> ma;
vector<pii> adj[MAX_N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i <m; i ++)
{
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
for(int i = 1; i <=n; i ++)
{
for(int u = 0; u < adj[i].size(); u ++)
ma[{i,adj[i][u].ss}] ++;
}
set<pair<pii,int>> s;
s.insert({{0,1},-1});
bool visited[n+1]; memset(visited,false,sizeof(visited));
int dist[n+1]; for(int i = 2; i <= n; i ++)dist[i] = MOD;
while(!s.empty())
{
pair<pii,int> u = *(s.begin());
s.erase(s.begin());
int d = u.ff.ff;
int node = u.ff.ss;
if(visited[node]) continue;
dist[node] = d;
int col = u.ss;
//cout << node << ' ' << d << ' ' << col << '\n';
visited[node] = true;
if(node == n)
{
cout << d;
exit(0);
}
for(auto e: adj[node])
{
if(visited[e.ff]) continue;
int occ = ma[{node,e.ss}];
if(e.ss == col)
occ --;
int nvd = d + (occ > 1);
if(dist[e.ff] > dist[node] + nvd)
{
dist[e.ff] = dist[node] + nvd;
if(nvd == d)
{
s.insert({{nvd,e.ff},-1});
}
else
s.insert({{nvd,e.ff},e.ss});
}
}
}
cout << -1;
}
/*
Identify problem diagram: Brute force, Greedy, Dynamic Programming, Divide and Conquer
Reformulate the problem into something more theoretical
!!!!! IMPLICIT GRAPH ??????
!!!!! PAY ATTENTION TO THE CONSTRAINTS: DP nD ? BF ? BITMASKING ?
!!!!! SOLVE THE SUBTASKS FIRST: IT'S TOTALLY OK NOT TO SOLVE THE PROBLEM ENTIRELY
Search for multiple approaches: select the seemingly optimal one
Remember that you're the king of CP
Change your approach
Imagine Corner cases before submitting
Don't spend too much time on the problem: move on !
*/
Compilation message
Main.cpp:26:1: warning: multi-line comment [-Wcomment]
26 | ////////////******SOLUTION******\\\\\\\\\\\
| ^
Main.cpp: In function 'int main()':
Main.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int u = 0; u < adj[i].size(); u ++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
10020 KB |
Output is correct |
| 2 |
Correct |
39 ms |
7104 KB |
Output is correct |
| 3 |
Correct |
101 ms |
11364 KB |
Output is correct |
| 4 |
Correct |
68 ms |
8604 KB |
Output is correct |
| 5 |
Incorrect |
373 ms |
30384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
