7 |
您所在的位置：网站首页 › 紧急头可以看的紧急头 › 7 |
7
|
一：题目
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。 输入格式: 输入第一行给出4个正整数N、M、S、D，其中N（2≤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算法，加了其他判断方法 三 上码： //有相同的的路径时 选择 顶点人数最多的 #include #include #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(i=0;iNv;i++){ scanf("%d",&a[i]); } for(i=0; iNv;i++){ for(j=0;jNv;j++){ if(i == j) G->GData[i][j] = 0; else G->GData[i][j] = infinite; } } for(k=0; kNe; 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(i=0;iNv;i++){ for(j=0;jNv;j++){ if(G->GData[i][j]!=infinite) printf("%d ",G->GData[i][j]); else printf("∞"); } printf("\n"); } } void putlu(int u,int v) { //通过v结点的上一结点查找到u结点，将路径存到栈s中，最后输出。 int s[60],k,i,l; k=0; l=path[v];//将3对应的上一个点1 入栈了 然而3并没有进数组 while(l!=u)//入栈 { s[k++]=l; l=path[l]; } printf("%d ",u); for(i=k-1;i>=0;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->Nv==2){//最短路径只有两个顶点 cist[end]=a[0]+a[1]; count[end]=1; path[1]=0; } else { for(i=0;iNv;i++){ count[i]=1; dist[i] = G->GData[begin][i]; if(i != begin) cist[i] = a[begin]+a[i]; else cist[i] = a[i]; } vis[0]=1; while (1) { int mv=-1; int min=infinite; for(i=0; iNv; i++){ if(vis[i] != 1 && dist[i] GData[mv][j]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 && min+G->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
但这个超时间。我优化了但还是过去 /** 思路： 这个就是单源点最短路径的变形，这里是出现了到达某个顶点出现相同的最短距离， 只不过是经过的点不一样，每个点给了相应的赋值，我们需要判断每一条路径上经过的 点，他们的值相加（每个点赋值），比较最大的那个就是救援队人数最多的， 选取他们作为救援最优路径 */ #include 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; mapm;//用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 > temp; m[i] = temp; } //矩阵初始化 for( int i = 0; i Nv; i++ ){ for( int j = 0; j Nv; j++ ){ if( i == j ) G->Date[i][j] = 0; else G->Date[i][j] = infinite; } } //矩阵赋值 for( int i = 0; i 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(i=0; iNv; i++){ for(j=0;jNv;j++){ if(G->Date[i][j] == infinite||G->Date[j][i] == infinite) printf("∞"); else cout |
【本文地址】