【每日一题】 UVA - 1599 Ideal Path 字典序最短路

时间：2021-02-06 03:52:44

题解：给一个1e5个点2e5条边，每个边有一个值，让你输出一条从1到n边的路径使得：条数最短的前提下字典序最小。

题解：bfs一次找最短路（因为权值都是1，不用dijkstra），再bfs一次存一下路径，4个月前的代码（忘了为什么搞得那么麻烦），wa了两天，今天看了一下题目，看了一下代码，改了一下初始化数组，直接过了orz

#define _CRT_SECURE_NO_WARNINGS

#include<cstring>

#include<cctype>

#include<cmath>

#include<cstdio>

#include<string>

#include<stack>

#include<list>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<sstream>

#include<iostream>

#include<algorithm>

//std::ios::sync_with_stdio(false);

using namespace std;

const int maxn = 2e5 + ;

vector<pair<int, int> >E[maxn];

int d[maxn];

int n, m;

void bfs(int n) {

    queue<int> Q;

    Q.push(n); d[n] = ;

    while (!Q.empty()) {

        int now = Q.front(); Q.pop();

        for (int i = ; i < E[now].size(); i++) {

            int v = E[now][i].first;

            if (d[v])continue;

            d[v] = d[now] + ;

            Q.push(v);

        }

    }

}

int ans[maxn];

int vis[maxn];

void bfs1() {

    for (int i = ; i <= n; i++)ans[i] = 1e9+;

    queue<int>Q;

    Q.push();

    while (!Q.empty()) {

        int now = Q.front(); Q.pop();

        if (vis[now])continue;

        vis[now] = ;

        int mn = 1e9 + ;

        for (int i = ; i < E[now].size(); i++) {

            int v = E[now][i].first;

            if (d[v] != d[now] - )continue;

            int w = E[now][i].second;

            mn = min(mn, w);

        }

        int diff = d[] - d[now];

        ans[diff] = min(ans[diff], mn);

        for (int i = ; i < E[now].size(); i++) {

            int v = E[now][i].first;

            if (d[v] != d[now] - )continue;

            int w = E[now][i].second;

            if (w == mn) Q.push(v);

        }

    }

}

void init() {

    memset(ans, , sizeof(ans));

    memset(vis, , sizeof(vis));

    memset(d, , sizeof(d));

    for (int i = ; i <= n; i++)E[i].clear();

}

int main() {

    while (cin >> n >> m) {

        init();

        for (int i = ; i <= m; i++) {

            int x, y, z;

            scanf("%d%d%d", &x, &y, &z);

            E[x].push_back(make_pair(y, z));

            E[y].push_back(make_pair(x, z));

        }

        bfs(n);

        bfs1();

        cout << d[] -  << endl;

        for (int i = ; i < d[] - ; i++)printf("%d%c", ans[i], i +  == d[] -  ? '\n' : ' ');// << ' ';|

    }

    //system("pause");

    return ;

}

/*

4 6

1 2 1

1 3 2

3 4 3

2 3 1

2 4 4

3 1 1

*/

相关文章