Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include <string>
- #include<algorithm>
- #include <iostream>
- #include <queue>
- #include<set>
- #include<cmath>
- #include<math.h>
- using namespace std;
- #define ll long long
- #define pll pair<long long, long long>
- #define mp make_pair
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #define cin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh];
- #define pcin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh].first»a[ghgh].second;
- #define cout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout<<a[ghgha]<<" ";
- #define pcout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout«a[ghgha].first«" "«a[ghgha].second«endl;
- const ll inf = 1e9 + 7, llinf = 1e18 + 123;
- void xru() {
- setlocale(LC_ALL, "rus");
- /*freopen(".in", "r", stdin);
- freopen(".out", "w", stdout);*/
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- int main()
- {
- xru();
- ll n, m;
- cin >> n >> m;
- vector<vector<ll>>check(n, vector<ll>(n, llinf));
- vector<ll>x(m), y(m), cnt(m);
- for (ll i = 0; i < m; i++) {
- cin >> x[i] >> y[i] >> cnt[i];
- x[i]--, y[i]--;
- if (x[i] == y[i]) continue;
- check[x[i]][y[i]] = min(check[ x[i] ][ y[i] ], cnt[i]);
- check[y[i]][x[i]] = check[x[i]][y[i]];
- }
- vector < vector<pll>>g(n);
- for (ll i = 0; i < m; i++) {
- if (x[i] == y[i] || check[x[i]][y[i]] == llinf) continue;
- g[x[i]].push_back({ y[i], check[x[i]][y[i]] });
- g[y[i]].push_back({ x[i], check[x[i]][y[i]] });
- check[x[i]][y[i]] = llinf;
- check[y[i]][x[i]] = llinf;
- }
- vector<pll>prev(n, { -1, inf });
- vector<ll>dist(n, inf);
- vector<bool>used(n, false);
- queue<ll>q;
- vector<vector<pll>> lg(n);
- q.push(n - 1);
- dist[n - 1] = 0;
- used[n - 1] = true;
- while (!q.empty()) {
- ll v = q.front();
- q.pop();
- for (ll i = 0; i < g[v].size(); i++) {
- pll to = g[v][i];
- if (!used[to.first]) {
- dist[to.first] = dist[v] + 1;
- lg[to.first].push_back({ v, to.second });
- lg[v].push_back(to);
- used[to.first] = true;
- q.push(to.first);
- }
- else {
- if (dist[v] + 1 == dist[to.first]) {
- lg[to.first].push_back({ v, to.second });
- lg[v].push_back(to);
- }
- }
- }
- }
- queue<ll>lq;
- vector<ll>minLdist(dist[0] + 1, inf);
- vector<ll>ldist(n, inf);
- vector<bool>lused(n, false), vlused(n, false);
- vector<ll>ans;
- ldist[0] = 0;
- lused[0] = true;
- lq.push(0);
- while (!lq.empty()) {
- ll lv = lq.front();
- // cout << lv << endl;
- lq.pop();
- if (!vlused[lv]) {
- //cout << lv << " ";
- for (ll i = 0; i < lg[lv].size(); i++) {
- pll lto = lg[lv][i];
- if (!lused[lto.first]) {
- minLdist[ ldist[lv] + 1 ] = min( minLdist[ldist[lv] + 1] , lto.second );
- }
- else {
- if (ldist[lv] + 1 == ldist[lto.first]) {
- minLdist[ldist[lv] + 1] = min(minLdist[ldist[lv] + 1], lto.second);
- }
- }
- }
- vlused[lv] = true;
- lq.push(lv);
- }
- else {
- for (ll i = 0; i < lg[lv].size(); i++) {
- pll lto = lg[lv][i];
- if (!lused[lto.first]) {
- ldist[lto.first] = ldist[lv] + 1;
- lused[lto.first] = true;
- if (lto.second == minLdist[ldist[lto.first]]) {
- lq.push(lto.first);
- }
- }
- }
- }
- }
- cout << minLdist.size() - 1<<endl;
- for (ll i = 1; i < minLdist.size(); i++) {
- cout << minLdist[i] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement