做外单网站有哪些,电子商务网站的建设包含哪些流程图,字体在线设计网站,制作响应式网站题目描述 做为一个资深驴友#xff0c;小新有一张珍藏的自驾游线路图#xff0c;图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况#xff0c;现在请你编写一个程序#xff0c;找出一条出发地到目的地之间的最短路径#xff0c;如果有多条路径最短#xff… 题目描述 做为一个资深驴友小新有一张珍藏的自驾游线路图图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况现在请你编写一个程序找出一条出发地到目的地之间的最短路径如果有多条路径最短则输出过路费最少的一条路径。输入 连续T组数据输入每组输入数据的第一行给出四个正整数N,Msd其中N(2 N 500)是城市数目城市编号从0N-1M是城市间高速公路的条数s是出发地的城市编号d是目的地的城市编号随后M行每行给出一条高速公路的信息表示城市1、城市2、高速公路长度、收费额中间以空格间隔数字均为整数且不超过500输入数据均保证有解。 输出 在同一行中输出路径长度和收费总额数据间用空格间隔。 示例输入 1
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20 示例输出 3 40 提示 #includebits/stdc.h #define inf 0x3f3f3f3f typedef struct node { int l;//高速公路的长度 int c;//收费额 }node; node a[501][501];//两城市间是否有关系 node dis[501]; int visit[501];//标记数组 int n,m,s,d; void low_dis_m()//找最短路径最少花费 { visit[s]1;//起点开始 int min,i,j,k,u; for(i0;in-1;i) { mininf; for(j0;jn;j)//找邻接点的最小路径 { if(!visit[j]mindis[j].l) { mindis[j].l; uj; } } visit[u]1; for(k0;kn;k) { if(a[u][k].linf)//u到k之间有公路 { if(dis[k].ldis[u].la[u][k].l||((dis[k].ldis[u].la[u][k].l)(dis[k].cdis[u].ca[u][k].c))) //找最短路径如果路径相等则找最小花费 {dis[k].ldis[u].la[u][k].l; dis[k].cdis[u].ca[u][k].c; } } } } printf(%d %d\n,dis[d].l,dis[d].c);//输出到目标城市的最小距离最小花费 } int main() { int t,v1,v2,i,j,w,z; scanf(%d,t); while(t--) { memset(a,inf,sizeof(a));//注意初始化a数组为无穷大 memset(visit,0,sizeof(visit)); memset(dis,0,sizeof(dis)); scanf(%d %d %d %d,n,m,s,d); for(i0;in;i) for(j0;jn;j) { if(ij) { a[i][j].la[i][j].c0; } } for(i1;im;i) { scanf(%d %d,v1,v2); scanf(%d %d,w,z); a[v1][v2].la[v2][v1].lw; a[v1][v2].ca[v2][v1].cz; } for(i0;in;i) { dis[i].la[s][i].l;//城市间的距离关系 dis[i].ca[s][i].c;//城市间的收费关系 } low_dis_m(); } }
