首页 > 代码库 > hdu 3790 最短路径问题(双重权值，dijkstra算法)

hdu 3790 最短路径问题(双重权值，dijkstra算法)

2024-07-17 15:15:52   217人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3790 

题目大意：题意明了，输出最短路径及其花费。

需要注意的几点：(1)当最短路径相同时，输出最小花费！！！

(2)更新路径的时候要注意更新花费。

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int INF=9999999; 5 int map[1010][1010],Min,n,cost[1010][1010],node[1010],vis[1010]; 6 int pr[1010]; 7  8 void set() 9 {10     for (int i=1; i<=n; i++)11     {12         vis[i]=0;13         node[i]=INF;14         pr[i]=INF;15         for (int j=1; j<=n; j++)16         {17             map[i][j]=INF;18             cost[i][j]=INF;19         }20     }21 }22 23 void dijkstra(int m)24 {25     int tm=m;26     vis[m]=1;27     node[m]=0;28     pr[m]=0;29     for (int k=2; k<=n; k++)30     {31         Min=INF;32         int M=INF;33         for (int i=1; i<=n; i++)34             if(!vis[i])35             {36                 if (node[i]>map[tm][i]+node[tm])37                 {38                     node[i]=map[tm][i]+node[tm];39                     pr[i]=cost[tm][i]+pr[tm];40                 }41                 else if(node[i]==map[tm][i]+node[tm])42                 {43                     if(pr[i]>cost[tm][i]+pr[tm])44                     {45                         node[i]=map[tm][i]+node[tm];46                         pr[i]=cost[tm][i]+pr[tm];47                     }48                 }49                 if (Min>node[i])50                 {51                     M=pr[i];52                     Min=node[i];53                     m=i;54                 }55                 else if (Min==node[i])56                 {57                     if(M>pr[i])58                     {59                         M=pr[i];60                         Min=node[i];61                         m=i;62                     }63                 }64             }65         vis[m]=1;66         tm=m;67     }68 }69 70 int main ()71 {72     int a,b,d,p,m;73     while(scanf("%d%d",&n,&m),n||m)74     {75         set();76         while (m--)77         {78             scanf("%d%d%d%d",&a,&b,&d,&p);79             if (map[a][b]>d)80             {81                 cost[a][b]=cost[b][a]=p;82                 map[a][b]=map[b][a]=d;83             }84             else if (map[a][b]==d)85             {86                 if (cost[a][b]>p)87                     cost[a][b]=cost[b][a]=p;88             }89         }90         scanf("%d%d",&a,&b);91         dijkstra(a);92         printf ("%d %d\n",node[b],pr[b]);93     }94 }

 


联系
我们