问题 D: 最短路径

简介: 问题 D: 最短路径

问题 D: 最短路径

[命题人 : 外部导入]

时间限制 : 1.000 sec 内存限制 : 32 MB


题目描述

有n个城市m条道路(n<1000, m<10000),每条道路有个长度,请找到从起点s到终点t的最短距离和经过的城市名。


输入

输入包含多组测试数据。


每组第一行输入四个数,分别为n,m,s,t。


接下来m行,每行三个数,分别为两个城市名和距离。


输出

每组输出占两行。


第一行输出起点到终点的最短距离。


第二行输出最短路径上经过的城市名,如果有多条最短路径,输出字典序最小的那条。若不存在从起点到终点的路径,则输出“can’t arrive”。


样例输入 Copy

3 3 1 3

1 3 3

1 2 1

2 3 1

样例输出 Copy

2

1 2 3


分析:

该题是涉及多条最短路径的最短路径问题,由于要输出最短路径,pre定义成vector<int>型数组,在采用dfs遍历最短路径时考虑字典序问题,典型的Dijkstra+Dfs应用。

值得注意一点,据说这题可能会输入重复的边,所以用邻接表在codeup上只能拿50分,建议直接用邻接矩阵。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxv=1001;
const int inf=10000000;
struct node{
  int v,weight;
};
vector<node>Adj[maxv] ;
bool vis[maxv];
int dis[maxv];
vector<int>pre[maxv];//记录路径 
//dijkstra算法
void dijkstra (int n,int s) {
  fill(vis,vis+n+1,false);
  fill(dis,dis+n+1,inf); //初始化dis和vis
  dis[s] =0;//这里求零点到各点最短距离
  for(int i=0;i<n;i++) //循环n次
  {    
      int min=inf,u=-1;
    for(int j=1;j<=n;j++) 
     //找最短距离点 ,这里可以用优先队列存储dis下标更快 
    {
      if(!vis[j]&&dis[j]<min)
      {
        u=j;
        min=dis[j];
      }
    }
    if(u==-1) return ;//没有找到 
    vis[u] =true;//标记已经找到的u 
    for(int j=0;j<Adj[u].size();j++) //更新dis 
    {
      int x=Adj[u][j].v;
      if(!vis[x])
      {
        if(dis[u]+Adj[u][j].weight<dis[x]){
        dis[x]=dis[u]+Adj[u][j].weight;
        pre[x].clear();
        pre[x].push_back(u);}
        else if(dis[u]+Adj[u][j].weight==dis[x])
        pre[x].push_back(u);
      }
  } 
} 
}
vector<int>path,temppath; 
void dfs(int s,int t){
  if(t==s){
    temppath.push_back(t);
    int k=1,a=path.size(),b=temppath.size();
    if(a){
      while(a>0&&b>0){
        if(temppath[b--]>path[a--]){
          k=0;break;
  }
  if(temppath[b]<path[a])break;
}
    }
    if(k)path=temppath;
    temppath.pop_back();
    return;
  }
    temppath.push_back(t);
  for(int i=0;i<pre[t].size();i++)
  {
    dfs(s,pre[t][i]);
  }
  temppath.pop_back();
}
int main(){
  int n,m,s,t;
  int x,y,w;
  node temp;
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for(int i=0;i<m;i++){
    scanf("%d%d%d",&x,&y,&w); 
    temp.weight=w;
    temp.v=x;
    Adj[y].push_back(temp);
    temp.v=y;
    Adj[x].push_back(temp);
  }
  dijkstra(n,s);
  if(dis[t]==inf)printf("can't arrive\n");
  else {
    dfs(s,t);
    printf("%d\n",dis[t]);
  for(int i=path.size()-1;i>=0;--i)printf("%d ",path[i]);}
  return 0;
}
相关文章
|
关系型数据库 测试技术 Serverless
【PolarDB Serverless】资源伸缩&压测 TPC-C 测评
【PolarDB Serverless】资源伸缩&压测 TPC-C 测评
156277 31
【PolarDB Serverless】资源伸缩&压测 TPC-C 测评
|
9月前
|
机器学习/深度学习 自然语言处理 搜索推荐
自注意力机制全解析:从原理到计算细节,一文尽览!
自注意力机制(Self-Attention)最早可追溯至20世纪70年代的神经网络研究,但直到2017年Google Brain团队提出Transformer架构后才广泛应用于深度学习。它通过计算序列内部元素间的相关性,捕捉复杂依赖关系,并支持并行化训练,显著提升了处理长文本和序列数据的能力。相比传统的RNN、LSTM和GRU,自注意力机制在自然语言处理(NLP)、计算机视觉、语音识别及推荐系统等领域展现出卓越性能。其核心步骤包括生成查询(Q)、键(K)和值(V)向量,计算缩放点积注意力得分,应用Softmax归一化,以及加权求和生成输出。自注意力机制提高了模型的表达能力,带来了更精准的服务。
10358 46
|
JavaScript 前端开发 Python
python执行js代码
本文档详细介绍如何安装Node.js环境及PyExecJS库,并提供示例代码展示其功能。首先,通过指定链接安装Node.js,安装完毕后可在命令行中输入`node --version`来验证安装是否成功。接着,使用`pip install PyExecJS`安装PyExecJS库,该库允许Python程序执行JavaScript代码。文档还提供了多个示例代码,展示了如何在Python环境中执行和编译JavaScript代码,并可以选择特定的JavaScript运行时环境,如Node.js或JScript。最后,通过具体案例展示了PyExecJS的功能与使用方法。
158 3
|
并行计算 PyTorch Linux
大概率(5重方法)解决RuntimeError: CUDA out of memory. Tried to allocate ... MiB
大概率(5重方法)解决RuntimeError: CUDA out of memory. Tried to allocate ... MiB
8971 0
|
12月前
|
缓存 前端开发 JavaScript
优化前端性能:实用技巧与策略
本文介绍了前端性能优化的重要性和多种实用技巧,包括减少HTTP请求、利用浏览器缓存、压缩资源文件、异步加载非关键资源、优化CSS和JavaScript、减少DOM操作、谨慎使用Web字体、优化第三方脚本、使用服务工作者及性能监测和分析,帮助提升网站性能和用户体验。
|
算法 数据可视化 机器人
ROS2教程01 ROS2介绍
本文是ROS2(机器人操作系统的下一代)的介绍教程,内容包括ROS2的诞生背景、核心功能、特点、框架以及与ROS1的比较。文章涵盖了ROS2的通信系统、框架和工具、生态系统、全球性社区支持、完全开源、跨平台特性、多机协同能力、实时系统支持和更强的稳定性。此外,还提供了ROS2架构的详细介绍资源链接,适合对ROS2感兴趣的读者学习和了解。
1560 1
|
传感器 人工智能 自动驾驶
智能交通系统:自动驾驶技术的社会影响
【9月更文挑战第27天】随着科技发展,智能交通系统与自动驾驶技术正革新交通领域,从提高交通效率与安全性到优化资源分配,其影响深远。自动驾驶技术基于AI与传感器,历经五个等级演进,促进交通流畅的同时减少人为驾驶错误。然而,技术进步亦引发就业市场变化、数据隐私及道德责任等问题,城市规划需适应新技术,加建充电站等设施。尽管存在挑战,智能交通系统仍有望重塑城市面貌,提升出行体验,实现更高效、环保的城市交通体系。
|
安全 前端开发 中间件
Python面试题:Django Web框架基础与进阶
【4月更文挑战第17天】本文详细梳理了Django面试中常考的基础和进阶问题,包括MTV架构、ORM、数据库迁移、视图模板、中间件、信号、表单验证、用户认证授权等,并指出易错点及规避策略。提供代码示例展示模型和视图的实现,助力开发者在面试中脱颖而出。
708 12
|
负载均衡 安全 API
Neutron(网络)
【8月更文挑战第19天】
337 3
|
存储
html动态爱心代码【二】(附源码)
html动态爱心代码【二】(附源码)
860 0