首页 > 其他分享 >7.1日报

7.1日报

时间:2024-07-03 17:00:10浏览次数:19  
标签:vexnum arcs 日报 路径 ++ v0 int 7.1

今天是小学期的第一天,也是数据结构小学期的第一天,今天老师说明了第一阶段的任务,五人成组,每个组员四道题,共20道题,我的四道题是最短路径(迪杰斯特拉算法)、希尔排序的实现、先序和中序构造二叉树  、矩阵运算,今天完成了第一道题最短路径(迪杰斯特拉算法),以下是题目要求

试实现迪杰斯特拉最短路径算法。

函数接口定义:

 
void ShortestPath_DIJ(AMGraph G, int v0);

其中 G 是基于邻接矩阵存储表示的有向图, v0表示源点

裁判测试程序样例:

 
#include <iostream>
using namespace std;

#define MaxInt 32767
#define MVNum 100 
typedef char VerTexType;
typedef int ArcType;

int *D=new int[MVNum];
bool *S=new bool[MVNum];
int *Path=new int[MVNum];

typedef struct{ 
    VerTexType vexs[MVNum]; 
    ArcType arcs[MVNum][MVNum]; 
    int vexnum,arcnum;
}AMGraph;

void CreateUDN(AMGraph &G){ 
    int i , j , k;
    cin >> G.vexnum >> G.arcnum;

    for(i = 0; i < G.vexnum; ++i){   
        cin >> G.vexs[i];       
    }

    for(i = 0; i < G.vexnum; ++i)            
        for(j = 0; j < G.vexnum; ++j)   
            G.arcs[i][j] = MaxInt;  

    for(k = 0; k < G.arcnum;++k){                            
        VerTexType v1 , v2;
        ArcType w;
        cin >> v1 >> v2 >> w;                                
        i = LocateVex(G, v1);  
        j = LocateVex(G, v2);        
        G.arcs[i][j] = w;                                    
        G.arcs[j][i] = G.arcs[i][j];                         
    }
}

void ShortestPath_DIJ(AMGraph G, int v0);

void DisplayPath(AMGraph G , int begin ,int temp ){
    if(Path[temp] != -1){
        DisplayPath(G , begin ,Path[temp]);
        cout << G.vexs[Path[temp]] << "->";
    }
}

int main()
{
    AMGraph G; 
    int i , j ,num_start , num_destination;
    VerTexType start , destination;
    CreateUDN(G);
    cin >> start >> destination;
    num_start = LocateVex(G , start);
    num_destination = LocateVex(G , destination);
    ShortestPath_DIJ(G , num_start);
    DisplayPath(G , num_start , num_destination);
    cout << G.vexs[num_destination]<<endl;
    return 0;
}
/* 请在这里填写答案 */

输入样例:

第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值,接下来依次输入arcnum行,每行输入3个值,前两个字符表示结点,后一个数表示两个结点之间边的权值。最后一行输入源点及终点。

6 8
012345
0 5 100
0 2 10
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0 5

输出样例:

输出源点到终点的最短路径。

0->4->3->5
我的代码:

void ShortestPath_DIJ(AMGraph G, int v0) {
// 初始化
for (int i = 0; i < G.vexnum; ++i) {
D[i] = G.arcs[v0][i]; // 从v0到各顶点的初始路径长度
S[i] = false; // 标记数组,表示顶点是否已加入最短路径树
if (i != v0 && D[i] < MaxInt) {
Path[i] = v0; // 如果存在直接路径,则设置路径的起点为v0
} else {
Path[i] = -1; // 无路径时设为-1
}
}
D[v0] = 0;
S[v0] = true; // 将源点v0加入最短路径树

// 迪杰斯特拉算法核心
for (int i = 1; i < G.vexnum; ++i) {
int min = MaxInt;
int k = v0;
// 选择当前路径长度最小的顶点
for (int j = 0; j < G.vexnum; ++j) {
if (!S[j] && D[j] < min) {
min = D[j];
k = j;
}
}
S[k] = true; // 将顶点k加入最短路径树
// 更新从顶点k出发可以到达的所有顶点的最短路径长度
for (int j = 0; j < G.vexnum; ++j) {
if (!S[j] && G.arcs[k][j] < MaxInt) {
if (D[k] + G.arcs[k][j] < D[j]) {
D[j] = D[k] + G.arcs[k][j];
Path[j] = k; // 更新路径信息
}
}
}
}
}

 

标签:vexnum,arcs,日报,路径,++,v0,int,7.1
From: https://www.cnblogs.com/lijianlongCode13/p/18282130

相关文章

  • 7.2日报
    今天是数据结构小学期的第二天,今天完成了第二道题希尔排序的实现,以下为题目要求:本题要求实现一趟希尔排序函数,待排序列的长度1<=n<=1000。函数接口定义: voidShellInsert(SqListL,intdk);其中L是待排序表,使排序后的数据从小到大排列。###类型定义: typedefintKey......
  • 7.3日报
    今天是数据结构小学期的第三天,今天完成了第三道题,以下为题目要求:题目要求用先序序列和中序序列构造一棵二叉树(树中结点个数不超过10个),并输出其后序序列。输入格式:在第一行中输入元素个数。第二行中输入先序序列,用空格分隔。第三行中输入中序序列,用空格分隔。输出格式:输......
  • OpenAI 向少部分用户推出 GPT-4o(S2S)模型;Meta 发布 3D Gen AI 模型丨 RTE 开发者日报
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点,......
  • 7.1 ~ 7.7
    7.1搬了校区。发现我们虽然是在西扩上课,但宿舍还是老校区的\(12\)人宿舍,输。不过教学楼好玩的东西还是挺多的。本来我们是和化奥组一个班,但因为物奥集训&&我们班人数过多(\(69\))把我们和生奥放在了一起;然后我们名义上的班主任还是张华,各种老师...很乱。无所谓,既来之......
  • 2024.7.1
    转盘锁可以把序列看出一个个元素,+1,-1看成转移,这就成了一个bfs还可以发现,\(a_0,a_1,a_2,a_3\tob_0,b_1,b_2,b_3=0,0,0,0\tob_0-a_0,b_1-a_1,b_2-a_2,b_3-a_3\)状态数只有\(10^4\)#include<bits/stdc++.h>usingnamespacestd;unord......
  • 微软预计年底实现实时语音界面;硅基智能开源 AI 数字人交互平台 Duix丨 RTE 开发者日报
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编......
  • 全球AI新闻速递7.1
    全球AI新闻速递1.科大讯飞发布讯飞星火V4.0。2.成都人形机器人创新中心:基于视觉扩散架构的人形机器人任务生成式模型R-DDPRM。3.安徽省人形机器人产业创新中心获批,将打造国内首创、世界领先研究基地。4.亳州牵手华为打造华佗中医药大模型。5.微软:推出视觉基础模型Fl......
  • 云原生周刊:Argo Rollouts 支持 Kubernetes Gateway API 1.0 | 2024.7.1
    开源项目KubetoolsRecommenderSystemKubetoolsRecommenderSystem(Krs)是一个基于GenAI的工具,用于帮助管理和优化Kubernetes集群。buoybuoy是Kubernetes的声明式TUI仪表板。你可以在JSON文件中定义仪表板,它将从Kubernetes集群中获取信息并构建仪表板,以便在......
  • springboot3(cloud 2022.0.0)整合seata1.7.1
    一、第一步下载对应版本的seata服务  二、修改conf下的application.yml配置注意:主要是连接nacos的一些配置:注册中心和服务发现的配置1#Copyright1999-2019Seata.ioGroup.2#3#LicensedundertheApacheLicense,Version2.0(the"License");4#you......
  • 2024.7.1 - 7.15
    Question1-[ABC360G]SuitableEditforLIS给定一个长度为\(n\)的序列\(A\),你可以执行如下操作恰好一次,最大化LIS的长度:选定一个下标\(x\)满足\(1\leqx\leqn\),选定一个任意的整数\(y\),然后将\(A_x\)替换为\(y\)。\(1\leqn\leq2\times10^5,1\leqA_i\le......