首页 > 代码库 > PAT-1030. Travel Plan (30)
PAT-1030. Travel Plan (30)
这道题目就是简单的dijkstra算法，典型的从几条路径中选出一条最优的路径。
disjkstra算法:
1,设初始点d[v]=0;==>findMinIndex（寻找未被访问的最小顶点）>>对该顶点相邻接的顶点进行伸缩(伸缩时候是否考虑顶点被访问呢？当然是要考虑的)
用pre数组开记录路径，最后用栈来模拟出调用路径。
这道题目的意思就是给你一个图，每一段距离之间距离和cost，求从以顶点到另外一个顶点距离最短的路径，如果存在多条路径最短的路径，那么就选择话费最小的那一条。今天PAT题目最后一道题目好像就是这个的加强版。这个题目只是给了三个测试用例，没啥奇葩数据，1A，爽啊。
后面再加入一个搜索版的。
#include<stdio.h>#include<vector>#include<stack>#include<iostream>using namespace std;#define MAX 510//vector<int> map[MAX] 保存一张图的时候可以考虑用vector邻接表的形式int map[MAX][MAX];int cost[MAX][MAX];int dv[MAX];int cv[MAX];int pre[MAX];bool visited[MAX];int maxInt=0xffffffff>>1;stack<int> path;int findMin(int n){ int min=maxInt,index=-1; for(int i=0;i<n;i++) { if(!visited[i]&&dv[i]<min) { min=dv[i]; index=i; } } return index;}int main(){ int n,m,s,d; int a,b,dis,cos; //freopen("1030-in.txt","r",stdin); //freopen("1030-out.txt","w",stdout); while(scanf("%d%d%d%d",&n,&m,&s,&d)!=EOF) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) map[i][j]=maxInt; } for(int i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&dis,&cos); map[a][b]=map[b][a]=dis; cost[a][b]=cost[b][a]=cos; } for(int i=0;i<n;i++) { dv[i]=cv[i]=maxInt; visited[i]=false; pre[i]=-1; } dv[s]=0; cv[s]=0; while(true) { int index=findMin(n); if(index==-1) break; visited[index]=true; for(int i=0;i<n;i++) { if(map[index][i]!=maxInt&&!visited[i]) { if(dv[i]>dv[index]+map[i][index]) { dv[i]=dv[index]+map[i][index]; cv[i]=cv[index]+cost[i][index]; pre[i]=index; } else if(dv[i]==dv[index]+map[i][index]&&cv[i]>cv[index]+cost[i][index]) { dv[i]=dv[index]+map[i][index]; cv[i]=cv[index]+cost[i][index]; pre[i]=index; } } } } int index=d; while(index!=-1) { path.push(index); index=pre[index]; } int top; while(!path.empty()) { top=path.top(); printf("%d ",top); //cout<<top<<" "; path.pop(); } printf("%d ",dv[d]); printf("%d\n",cv[d]); } return 0;}
PAT-1030. Travel Plan (30)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。