首页 > 代码库 > Choose the best route(迪杰斯特拉）

Choose the best route(迪杰斯特拉）

2024-07-10 00:21:24   217人阅读

     通过做这题，发现了自己的问题很大，做题不是贴代码，而是要了解思想；这题考的是有一个起点的集合，求起点集合到一个终点的最短距离，

本来想用Floy的但一看map[1000][1000]超时，有向图，逆序建邻接矩阵，这样就成了一个终点到所有点的最短路了。

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #define N 1000001 5 int n,m,s,w; 6 int map[1001][1001]; 7 int v[1001],dis[1001]; 8 void DJ() 9 {10     memset(v,0,sizeof(v));11     for(int i=1;i<=n;i++)12         dis[i]=N;13     dis[s]=0;14     int min,k;15     for(int i=1;i<=n;i++)16     {17         min=N;18         for(int j=1;j<=n;j++)19         {20             if(v[j]==0&&min>dis[j])21             {22                 min=dis[j];23                 k=j;24             }25         }26             if(min==N) break;27             v[k]=1;28             for(int j=1;j<=n;j++)29             {30                 if(v[j]==0&&map[k][j]+dis[k]<dis[j])31                     dis[j]=dis[k]+map[k][j];32             }33 34     }35 }36 int main()37 {38     int x,y,z;39     while(scanf("%d%d%d",&n,&m,&s)!=EOF)40     {41         for(int i=1;i<=n;i++)42         {43             for(int j=1;j<=n;j++)44             {45                 map[i][j]=N;46             }47             map[i][i]=0;48         }49         while(m--)50         {51             scanf("%d%d%d",&x,&y,&z);52             if(map[y][x]>z)53             {54                 map[y][x]=z;55             }56         }57         DJ();58         scanf("%d",&w);59         int bb[1001];60         for(int i=0;i<w;i++)61         {62             scanf("%d",&bb[i]);63         }64         DJ();65 66         int min=N;67         for(int i=0;i<w;i++)68             if(dis[bb[i]]<min)69             min=dis[bb[i]];70 71             if(min==N)72                 printf("-1\n");73             else74         printf("%d\n",min);75     }76     return 0;77 }

 


联系
我们