【1030】Travel Plan (30 分)

简介: 【1030】Travel Plan (30 分)【1030】Travel Plan (30 分)
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//dijkstra + DFS
const int MAXV=510;  //最大顶点数
const int INF=0x3fffffff; //无穷大
//n为顶点数,m为边数,st和ed分别为起点和终点
//G为距离矩阵,cost为花费矩阵
//d[]记录最短距离,minCost记录最短路径上的最小花费
int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
int d[MAXV],minCost=INF;
bool vis[MAXV]={false}; //vis[i]==true表示顶点i已访问,初值均为false
vector<int> pre[MAXV];//前驱
vector<int> tempPath,path; //临时路径,最优路径
void Dijkstra(int s){  //s为起点
  fill(d,d+MAXV,INF); //fill函数将整个d数组赋为INF
  d[s]=0;  //起点s到达自身的距离为0
  for(int i=0;i<n;i++){  //遍历n个顶点
    int u=-1,MIN=INF;  //u使d[u]最小,MIN存放该最小的d[u]
    for(int j=0;j<n;j++){  //找到未访问的顶点中d[]最小的
      if(vis[j] == false && d[j] <MIN){
        u=j;
        MIN=d[j];
      }
    }
    //找不到小于INF的d[u],说明剩下的顶点和起点不连通
    if(u == -1)  return ;
    vis[u]=true;  //标记u为已访问
    for(int v=0;v<n;v++){ 
      //如果v未访问 && u能够到达v
      if(vis[v]==false && G[u][v] !=INF){
        if(d[u]+G[u][v] < d[v]){ //以u为中介点使d[v]更小
          d[v]=d[u]+G[u][v]; //优化d[v]
          pre[v].clear(); //清空pre[v]
          pre[v].push_back(u); //u为v的前驱
        }else if(d[u]+G[u][v] == d[v]) {//找到相同长度的路径
          pre[v].push_back(u); //u为v的前驱之一
        }
      }
    }
  }
}
void DFS(int v){ //v为当前结点
  if(v == st){  //递归边界,到达叶子结点(路径起点)
    tempPath.push_back(v);
    int tempCost=0; //记录当前路径的花费之和
    for(int i=tempPath.size()-1;i>0;i--){ //倒着访问
      //当前结点id、下个结点idNext
      int id=tempPath[i] , idNext=tempPath[i-1];
      tempCost += cost[id][idNext]; //增加边id->idNext的边权
    }
    if(tempCost < minCost){  //如果当前路径的边权之和更小  
      minCost=tempCost;  //更新minCost
      path=tempPath; //更新path
    }
    tempPath.pop_back();//将刚才加入的结点删除
    return;
  }
  tempPath.push_back(v); //将当前访问结点加入临时路径tempPath最后面
  for(int i=0;i<pre[v].size();i++){
    DFS(pre[v][i]);
  }
  tempPath.pop_back();//遍历完所有前驱结点,将当前结点v删除
}
int main(){   
  scanf("%d%d%d%d",&n,&m,&st,&ed); 
  int u,v;
  fill(G[0],G[0]+MAXV*MAXV,INF);//初始化图G
  fill(cost[0],cost[0]+MAXV*MAXV,INF);
  for(int i=0; i<m; i++){
    scanf("%d%d",&u,&v); 
    scanf("%d%d",&G[u][v], &cost[u][v]);
    G[v][u]=G[u][v]; //因为是无向图
    cost[v][u]=cost[u][v]; 
  }
  Dijkstra(st);
  DFS(ed); //获得最优路径
  for(int i=path.size()-1; i>=0; i--){
    printf("%d ",path[i]); //倒着输出路径上的结点
  }
  printf("%d %d\n",d[ed],minCost);  //最短距离,最短路径上的最小花费
  system("pause"); 
    return 0;   
}
相关文章
|
1天前
|
云安全 数据采集 人工智能
古茗联名引爆全网,阿里云三层防护助力对抗黑产
阿里云三层校验+风险识别,为古茗每一杯奶茶保驾护航!
古茗联名引爆全网,阿里云三层防护助力对抗黑产
|
5天前
|
人工智能 中间件 API
AutoGen for .NET - 架构学习指南
《AutoGen for .NET 架构学习指南》系统解析微软多智能体框架,涵盖新旧双架构、核心设计、技术栈与实战路径,助你从入门到精通,构建分布式AI协同系统。
296 142
|
5天前
|
Kubernetes 算法 Go
Kubeflow-Katib-架构学习指南
本指南带你深入 Kubeflow 核心组件 Katib,一个 Kubernetes 原生的自动化机器学习系统。从架构解析、代码结构到技能清单与学习路径,助你由浅入深掌握超参数调优与神经架构搜索,实现从使用到贡献的进阶之旅。
278 139
|
1天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
264 0
|
2天前
|
传感器 人工智能 算法
数字孪生智慧水务系统,三维立体平台,沃思智能
智慧水务系统融合物联网、数字孪生与AI技术,实现供水全流程智能监测、预测性维护与动态优化。通过实时数据采集与三维建模,提升漏损控制、节能降耗与应急响应能力,推动水务管理从经验驱动迈向数据驱动,助力城市水资源精细化、可持续化管理。
251 142
|
1天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
本文介绍RAG(检索增强生成)技术,结合Spring AI与本地及云知识库实现学术分析AI应用,利用阿里云Qwen-Plus模型提升回答准确性与可信度。
167 90
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
|
16天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
1天前
|
机器学习/深度学习 人工智能 运维
智能照明稳压节能控制器,路灯节能稳压系统,沃思智能
智能照明调控柜集电力分配、远程控制与能耗管理于一体,支持自动调光、场景切换与云平台运维,广泛应用于市政、商业及工业领域,显著节能降耗,助力智慧城市建设。
178 137
kde
|
1天前
|
人工智能 关系型数据库 PostgreSQL
n8n Docker 部署手册
n8n是一款开源工作流自动化平台,支持低代码与可编程模式,集成400+服务节点,原生支持AI与API连接,可自托管部署,助力团队构建安全高效的自动化流程。
kde
184 3