【例题 6-20 UVA - 1599】Ideal Path
20 path UVa 例题
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
逆向做一遍bfs. 得到终点到某个点的最短距离。 这样,我们从起点顺序的时候。 就能知道最短路的下一步是要走哪里了。 这样,我们从起点也开始做一遍bfs. 然后根据逆序的bfs得知下一步该往哪些点走。 每次优先走最小的字典序边即可。 多个最小的,就每个都走一遍试试。 6 6 1 2 3 1 3 3 2 4 5 3 5 1 4 6 1 5 6 100 ans = 3->1->100 ↑↑这组数据可以hack网上好多人(>=1)的做法,数据里没有这组。 如果出现前一段路不是最小字典序了,就要结束这一段路了,不能继续往下走。 (或者,这样说,字典序最小的最短路不会到x这个节点来,那么就不能从x再继续往下走了)【代码】
/*
1.Shoud it use long long ?
2.Have you ever test several sample(at least therr) yourself?
3.Can you promise that the solution is right? At least,the main ideal
4.use the puts("") or putchar() or printf and such things?
5.init the used array or any value?
6.use error MAX_VALUE?
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n,m,dis[N+10];
int vis[N+10];
vector < pair<int,int> > g[N+100];
queue <int> dl;
int a[N+10];
int main(){
#ifdef LOCAL_DEFINE
freopen("F:\\c++source\\rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
while (cin >> n >> m){
memset(vis,0,sizeof vis);
for (int i = 1;i <= n+1;i++) a[i] = (int) 1e9+7;
for (int i = 1;i <= n;i++) g[i].clear();
for (int i = 1;i <= m;i++){
int x,y,z;
cin >>x>>y>>z;
g[x].push_back(make_pair(y,z));
g[y].push_back(make_pair(x,z));
}
memset(dis,255,sizeof dis);
dis[n] = 0;
dl.push(n);
while (!dl.empty()){
int x = dl.front();
dl.pop();
for (int i = 0;i < (int)g[x].size();i++){
int y = g[x][i].first;
if (dis[y]==-1){
dis[y] = dis[x] + 1;
dl.push(y);
}
}
}
vis[1] = 1;
dl.push(1);
while (!dl.empty()){
int x = dl.front();
dl.pop();
if (vis[x]>a[dis[x]+1]) continue; //vis[x]就是路径中到x的前一条边的最小权值,如果它不是前一条边的最小字典序就跳过
int mi = (int) 1e9 + 10;
for (int i = 0;i < (int) g[x].size();i++){
int y = g[x][i].first;
if (dis[y]==dis[x]-1){
mi = min(mi,g[x][i].second);
}
}
a[dis[x]] = min(mi,a[dis[x]]);
for (int i = 0;i < (int) g[x].size();i++){
int y = g[x][i].first;
if (dis[y]==dis[x]-1 && g[x][i].second==mi){
if (!vis[y]) dl.push(y);
if(!vis[y] || vis[y]>mi) vis[y] = mi;
}
}
}
cout << dis[1] << endl;
for (int i = dis[1];i >= 1;i--) {
cout << a[i];
if (i==1) cout << endl;else cout << ' ';
}
}
return 0;
}
相关文章
- 每天20分钟之java使用grpc
- 科学瞎想系列之一四四 电机绕组(20)
- 2022-09-20 里氏替换
- 深入Linux:更新PATH路径(linux更新path)
- Linux下设置多个Path的方法(linux多个path)
- 路径配置Linux系统中PATH路径的配置(linux系统path)
- Linux系统下设置 PATH 环境变量(linux设置环境变量path)
- 20周年纪念:OpenBSD发布5.8版本
- 腾讯云数据库MySQL 8.0 正式上线:“80后”渐感吃力,“20后”茁壮成长
- 【Linux恢复PATH:让你的路径重获新生】(linux恢复path)
- 智能音箱背后的“声优”:一百多人里挑出一个声音 两个月录了20万字
- 20年后的机器人不如猫?Google的AI专家和Amazon的VP打了一个赌
- 耗资20亿美元的 “科学废墟”
- 20款效果非常棒的jQuery插件小结分享
- 20个最新的jQuery插件
- 20个2014年最优秀的PHP框架回顾