南昌网站建设制作与维护,网站怎么解析域名解析,网站运营的案例,做网站小程序多少钱一#xff1a;题目
作为一个城市的应急救援队伍的负责人#xff0c;你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候#xff0…一题目
作为一个城市的应急救援队伍的负责人你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你的任务是带领你的救援队尽快赶往事发地同时一路上召集尽可能多的救援队。
输入格式: 输入第一行给出4个正整数N、M、S、D其中N2≤N≤500是城市的个数顺便假设城市的编号为0 ~ (N−1)M是快速道路的条数S是出发地的城市编号D是目的地的城市编号。
第二行给出N个正整数其中第i个数是第i个城市的救援队的数目数字间以空格分隔。随后的M行中每行给出一条快速道路的信息分别是城市1、城市2、快速道路的长度中间用空格分开数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式: 第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔输出结尾不能有多余空格。
输入样例: 4 5 0 3 20 30 40 10 0 1 1 1 3 2 0 3 3 0 2 2 2 3 2 结尾无空行 输出样例: 2 60 0 1 3 结尾无空行
二 思路
dij算法加了其他判断方法
三 上码
//有相同的的路径时 选择 顶点人数最多的
#includestdio.h
#includestdlib.h
#define infinite 99999
typedef struct GNode* PtrGNode;
typedef struct GNode{int Nv;int Ne;int GData[1000][1000];
}gnode;
int begin,end,a[1000];//a数组存每个城市的救援队人数;
int path[1000]{-1}; void CreatGNode(PtrGNode G){int i,j,w,k;scanf(%d%d%d%d,G-Nv,G-Ne,begin,end);for(i0;iG-Nv;i){scanf(%d,a[i]);}for(i0; iG-Nv;i){for(j0;jG-Nv;j){if(i j)G-GData[i][j] 0;elseG-GData[i][j] infinite;}}for(k0; kG-Ne; k){scanf(%d%d%d,i,j,w);G-GData[i][j] w;G-GData[j][i] w;}
}
void outprint(PtrGNode G){int i,j;for(i0;iG-Nv;i){for(j0;jG-Nv;j){if(G-GData[i][j]!infinite)printf(%d ,G-GData[i][j]);elseprintf(∞);}printf(\n);}
}void putlu(int u,int v)
{//通过v结点的上一结点查找到u结点将路径存到栈s中最后输出。 int s[60],k,i,l;k0;lpath[v];//将3对应的上一个点1 入栈了 然而3并没有进数组 while(l!u)//入栈 {s[k]l;lpath[l];}printf(%d ,u);for(ik-1;i0;i--)printf(%d ,s[i]);printf(%d,v);//3没有进数组
}void Dijkstra(PtrGNode G){int dist[1000];//存路径长度int cist[1000];//记录人数 一直在变 int rist[1000];//存人数 到达每个顶点的人数不变 int vis[1000]{0};//记录已经遍历的点int count[1000]; //记录最短路径条数 int i,j;//因为从begin开始的点 也有人数if(G-Nv2){//最短路径只有两个顶点 cist[end]a[0]a[1];count[end]1;path[1]0;}else{for(i0;iG-Nv;i){count[i]1;dist[i] G-GData[begin][i];if(i ! begin)cist[i] a[begin]a[i];elsecist[i] a[i];}vis[0]1;while (1){int mv-1;int mininfinite;for(i0; iG-Nv; i){if(vis[i] ! 1 dist[i] min){mindist[i];mvi;}}if(mv-1)break;vis[mv]1;for(j0;jG-Nv;j){if(vis[j]!1 minG-GData[mv][j]dist[j]){dist[j] minG-GData[mv][j];cist[j] cist[mv]a[j];//根据路径长度已经判断 比原来路径短 而其人数必定时增加的 // rist[j]rist[mv]a[j]; count[j] count[mv];path[j] mv;}else if(vis[j]!1 minG-GData[mv][j] dist[j]){//处理相同路径长度时 选择人数多的count[j] count[mv]; if((cist[mv]a[j])cist[j]){ cist[j] cist[mv]a[j];// rist[j]rist[mv]a[j]; //更新 已经找到最短路径的那一个顶点 已经确认的到达这个顶点的总人数 path[j] mv;}}}}
}printf(%d %d,count[end],cist[end]);printf(\n);putlu(begin,end);}
int main(){PtrGNode G;G(PtrGNode)malloc(sizeof(struct GNode));CreatGNode(G);Dijkstra(G);//outprint(G);
}
//2 1 0 1
//20 30
//0 1 2//6 9 0 3
//10 20 30 40 50 60
//0 1 1
//0 2 3
//0 3 6
//0 4 3
//0 5 2
//1 2 2
//2 3 3
//3 4 3
//4 5 1四上超时的码这是我二刷是做的上面是第一次做的
但这个超时间。我优化了但还是过去
/**思路这个就是单源点最短路径的变形这里是出现了到达某个顶点出现相同的最短距离只不过是经过的点不一样每个点给了相应的赋值我们需要判断每一条路径上经过的点他们的值相加每个点赋值比较最大的那个就是救援队人数最多的选取他们作为救援最优路径
*/
#includebits/stdc.h
using namespace std;#define infinite 9999
typedef struct GNode* PtrGraph;
typedef struct GNode{int Nv;int Ne;int Date[501][501];
}gnode;int N,M,S,D;
mapint,intm;//用map容器进行储存每个结点的救援队数量
int path[501] { S };//将路径的初始值设为开始的那个点 //邻接矩阵储存图
void createGraph(PtrGraph G){cin N M S D;G-Nv N;G-Ne M;for( int i 0; i N; i ){int temp;cin temp;m[i] temp; }//矩阵初始化for( int i 0; i G-Nv; i ){for( int j 0; j G-Nv; j ){if( i j )G-Date[i][j] 0;elseG-Date[i][j] infinite; }}//矩阵赋值for( int i 0; i G-Ne; i ){int a,b,c;cin a b c; G-Date[a][b] c;G-Date[b][a] c;} } //输出矩阵
void outPutGNode(PtrGraph G){int i,j;for(i0; iG-Nv; i){for(j0;jG-Nv;j){if(G-Date[i][j] infinite||G-Date[j][i] infinite)printf(∞);elsecout G-Date[i][j] ;}printf(\n);}
}
//求路径上救援队数量
int PathSum( int x ){int sum m[x];while( path[x] ! x ){x path[x];summ[x];}return sum;
}
//求路径
void PathWay(int x){stackints;s.push(x);while(path[x] ! x ){x path[x];s.push(x); }while( !s.empty() ){if( s.size() ! 1 )cout s.top() ;elsecout s.top();s.pop(); }} //单源点最短路径
void dij(PtrGraph G){int dist[501] {0};int visited[501] {0};int vis[501] {0};
// int path[501] { S };//将路径的初始值设为开始的那个点 int count[501];//记录路数 for( int i 0; i G-Nv; i ){count[i] 1;//初始化为1即开始点到每个点的路数为1条 dist[i] G-Date[S][i];//将开始的那一行赋值给dist }visited[S] 1;vis[S] 1;while(1){int m -1;int min infinite;//求取最小值 for(int i 0; i G-Nv; i ){if( dist[i] min visited[i] ! 1){min dist[i];m i;} }//说明没找到最小值 即代表访问完了即便图是不连通的 那也求不出最小值了 if( m -1 ){break; }visited[m] 1; //更新 for( int i 0; i G-Nv; i ){if( visited[i] ! 1 dist[m] G-Date[m][i] dist[i] ){dist[i] dist[m] G-Date[m][i];path[i] m; count[i] count[m];//如果从开始的点S到 m 有两条路那么在更新最短路径时 //需要经过m的话那么m的路数将赋值给 更新的结点 } } }//这个循环主要是处理相同的最短路径 while(1){int m -1;int min infinite;//求取最小值 for(int i 0; i G-Nv; i ){if( dist[i] min vis[i] ! 1){min dist[i];m i;} }//说明没找到最小值 即代表访问完了即便图是不连通的 那也求不出最小值了 if( m -1 ){break; }vis[m] 1; //出现相同的路径 for( int i 0; i G-Nv; i ){if( vis[i] ! 1 dist[m] G-Date[m][i] dist[i] ){ count[i] count[i] count[m];//更新路数 int temp path[i];//将原来路径存下来万一相等的路径没有原来的路径上救援队人数多 还可以改回来 int a PathSum(i);path[i] m;int b PathSum(i);if( a b ){//原来的路径人数多 path[D] temp;//改回原来的路径 } } } }int Sumrescue PathSum(D);//救援队数量 cout count[D] Sumrescue endl;PathWay(D);}int main(){PtrGraph G (PtrGraph)malloc(sizeof (struct GNode));createGraph(G);dij(G);} //4 5 0 3
//20 30 40 10
//0 1 1
//1 3 2
//0 3 3
//0 2 1
//2 3 2//6 8 0 3
//10 20 30 40 50 60
//0 1 1
//0 2 3
//0 3 6
//0 4 3
//0 5 2
//1 2 2
//3 4 3
//4 5 1
加油boy
