首页 > 代码库 > 题目1008：最短路径问题
题目1008：最短路径问题
- 题目描述：
- 给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
- 输入：
- 输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
- 输出：
- 输出 一行有两个数， 最短距离及其花费。
- 样例输入：
3 21 2 5 62 3 4 51 30 0
- 样例输出：
9 11
---------------------------------------------------------------------
贴个别人用邻接表的代码：
1 //邻接表+dijk算法 2 3 #include <iostream> 4 #include <cstdio> 5 #include <cstring> 6 7 using namespace std; 8 9 #define inf 10000000 10 const int Maxn = 200005; 11 int N,M; 12 struct Edge{ 13 int v,next; 14 int dt,ct; 15 }edge[Maxn];//边数 16 int first[1005]; 17 int r,s,t; 18 int vis[1005]; 19 struct BNode{ 20 int dist,cost; 21 }P[1005]; //节点信息 22 23 //相当于链表的头插发，很有意思。比用邻接矩阵高效多了 24 void addedge(int u, int v, int d, int p) 25 { 26 edge[r].next = first[u]; 27 edge[r].v = v; 28 edge[r].dt = d; 29 edge[r].ct = p; 30 first[u] = r; 31 r++; 32 } 33 34 int findminode()//在那么多节点中找最小的 35 { 36 int i,Maxn = inf; 37 int index = 0; 38 for(i = 1; i<=N; i++) 39 if(P[i].dist<Maxn && !vis[i]) 40 { 41 Maxn = P[i].dist; 42 index = i; 43 } 44 //注意，如果存在多个相同的最短路径，要返回最小花费的节点 45 if(index) 46 { 47 for(i = 1; i<=N; i++) 48 if(P[i].cost<P[index].cost && !vis[i])index = i; 49 } 50 return index; 51 } 52 53 void solve() 54 { 55 int i; 56 for(i = 1; i<=N; i++) 57 P[i].dist = P[i].cost = inf; 58 P[s].dist = P[s].cost = 0; 59 memset(vis,0,sizeof(vis)); 60 int index = 1; 61 while(index<N)//更新N-1次就够了 62 { 63 int x = findminode(); 64 if(!x)break; 65 vis[x] = 1; index++; 66 for(i = first[x]; i!=-1; i = edge[i].next) 67 { 68 int v = edge[i].v; 69 if(P[x].dist+edge[i].dt<P[v].dist && !vis[v])//更新节点 70 { 71 P[v].dist = P[x].dist+edge[i].dt; 72 P[v].cost = P[x].cost+edge[i].ct; 73 } 74 else if(P[x].dist+edge[i].dt == P[v].dist && !vis[v])//如果存在多条最短路径，更新最小花费节点 75 { 76 if(P[x].cost+edge[i].ct<P[v].cost)P[v].cost = P[x].cost+edge[i].ct; 77 } 78 } 79 } 80 cout<<P[t].dist<<‘ ‘<<P[t].cost<<endl; 81 } 82 83 int main() 84 { 85 int i,u,v,d,p; 86 while(scanf("%d%d",&N,&M)!=EOF) 87 { 88 if(N == 0 && M == 0)break; 89 memset(first,-1,sizeof(first)); 90 r = 0; 91 for(i = 0; i<M; i++) 92 { 93 scanf("%d%d%d%d",&u,&v,&d,&p); 94 addedge(u,v,d,p); 95 addedge(v,u,d,p); 96 } 97 scanf("%d%d",&s,&t); 98 solve(); 99 }100 return 0;101 }
自己的代码，但是stack overflow了～原因应该是递归太深，导致占用堆栈过多。。
1 #include<stdio.h> 2 #define M 10000 3 #define N 1000 4 #include<stdlib.h> 5 struct L{ 6 int a,b,d,p; 7 }l0[M]; 8 void search(int n0,int d0,int p0,int s0,struct L q0); 9 int x; 10 int o[M][2];//存长度和花费 11 int m,n; 12 int s,t; 13 int main(int argc, char const *argv[]) 14 { 15 int n0,d0,p0; 16 int i; 17 int min; 18 struct L q0;//存上一条边信息 19 scanf("%d %d",&n,&m); 20 while(m!=0&&n!=0) 21 { 22 for(i=0;i<m;i++) 23 scanf("%d %d %d %d",&l0[i].a,&l0[i].b,&l0[i].d,&l0[i].p); 24 scanf("%d %d",&s,&t); 25 // printf("---1---\n"); 26 x=0; 27 q0.a=0;q0.b=0;q0.d=0;q0.p=0; 28 d0=0; 29 p0=0; 30 n0=1; 31 // printf("---2---\n"); 32 search(n0,d0,p0,s,q0); 33 // printf("---3---\n"); 34 min=0; 35 for(i=1;i<x;i++) 36 if((o[min][0]==o[i][0]&&o[min][1]>o[i][1])||o[min][0]>o[i][0]) 37 min=i; 38 printf("%d %d\n",o[min][0],o[min][1]); 39 // printf("---4---\n"); 40 scanf("%d %d",&n,&m); 41 } 42 return 0; 43 } 44 void search(int n0,int d0,int p0,int s0,struct L q0) 45 { 46 int i,count1,count2; 47 struct L *l1,*l2; 48 l1=(struct L*)malloc(sizeof(struct L)*100); 49 l2=(struct L*)malloc(sizeof(struct L)*100); 50 // printf("search\n");// 51 count1=count2=0; 52 // printf("%d\n",n0);// 53 n0++; 54 for(i=0;i<m;i++) 55 { 56 if(l0[i].a!=q0.a||l0[i].b!=q0.b||l0[i].d!=q0.d||l0[i].p!=q0.p) 57 { 58 if(l0[i].a==s0) 59 { 60 l1[count1]=l0[i]; 61 count1++; 62 } 63 else if(l0[i].b==s0) 64 { 65 l2[count2]=l0[i]; 66 count2++; 67 } 68 } 69 } 70 if(count1==0) 71 free(l1); 72 else 73 { 74 for(i=0;i<count1;i++) 75 { 76 if(l1[i].b==t&&n0==n) 77 { 78 79 o[x][0]=d0+l1[i].d; 80 o[x][1]=p0+l1[i].p; 81 x++; 82 } 83 else 84 { 85 q0=l1[i]; 86 d0=d0+l1[i].d; 87 p0=p0+l1[i].p; 88 s0=l1[i].b; 89 search(n0,d0,p0,s0,q0); 90 } 91 } 92 93 free(l1); 94 } 95 if(count2==0) 96 free(l1); 97 else 98 { 99 for(i=0;i<count2;i++)100 {101 if(l2[i].a==t&&n0==n)102 {103 o[x][0]=d0+l2[i].d;104 o[x][1]=p0+l2[i].p;105 x++;106 }107 else108 {109 q0=l2[i];110 d0=d0+l2[i].d;111 p0=p0+l2[i].p;112 s0=l2[i].a;113 search(n0,d0,p0,s0,q0);114 }115 }116 free(l2);117 }118 }
数据结构这块还是没掌握好～
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。