1599 - Ideal Path （UVA）

题目链接如下：

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4474

这道题也是看了刘汝佳的思路才写出来的....

代码如下：

#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
#include <map>
const int maxx = 100005;
const int maxColor = 1e9 + 1;
// #define debugstruct node{int id, color;node(int _id, int _color): id(_id), color(_color){}
};
int n, m, u, v, c, k, curr, minn;
std::map<int, std::vector<node>> mp;
int d[maxx], pre[maxx], preColor[maxx];
bool vis[maxx];void bfs1(){std::deque<int> dq;dq.push_back(n);d[n] = 0;vis[n] = true;while (!dq.empty()){curr = dq.front();dq.pop_front();for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (!vis[temp]){d[temp] = d[curr] + 1;vis[temp] = true;dq.push_back(temp);}}}
}void bfs2(){std::deque<int> dq;dq.push_back(1);while (!dq.empty()){curr = dq.front();dq.pop_front();minn = maxColor;for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (d[temp] == d[curr] - 1){minn = std::min(minn, mp[curr][i].color);}}for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (d[temp] == d[curr] - 1 && mp[curr][i].color == minn){if (!pre[temp]){dq.push_back(temp);}if (!pre[temp] || preColor[temp] > minn){pre[temp] = curr;preColor[temp] = minn;}}}}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d %d", &n, &m) == 2){mp.clear();std::fill(d, d + n + 1, -1);std::fill(vis, vis + n + 1, false);std::fill(pre, pre + n + 1, 0);std::fill(preColor, preColor + n + 1, -1);while (m--){scanf("%d %d %d", &u, &v, &c);if (u != v){mp[u].push_back(node(v, c));mp[v].push_back(node(u, c));}}bfs1();bfs2();std::vector<int> path;curr = n;do {path.push_back(preColor[curr]);curr = pre[curr];} while (curr != 1);reverse(path.begin(), path.end());printf("%d\n", path.size());for (int i = 0; i < path.size(); ++i){printf("%d%s", path[i], i == path.size() - 1 ? "\n" : " ");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}