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

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

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

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

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

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int INF=;

 int map[][],Min,n,cost[][],node[],vis[];

 int pr[];

 void set()

 {

     for (int i=; i<=n; i++)

     {

         vis[i]=;

         node[i]=INF;

         pr[i]=INF;

         for (int j=; j<=n; j++)

         {

             map[i][j]=INF;

             cost[i][j]=INF;

         }

     }

 }

 void dijkstra(int m)

 {

     int tm=m;

     vis[m]=;

     node[m]=;

     pr[m]=;

     for (int k=; k<=n; k++)

     {

         Min=INF;

         int M=INF;

         for (int i=; i<=n; i++)

             if(!vis[i])

             {

                 if (node[i]>map[tm][i]+node[tm])

                 {

                     node[i]=map[tm][i]+node[tm];

                     pr[i]=cost[tm][i]+pr[tm];

                 }

                 else if(node[i]==map[tm][i]+node[tm])

                 {

                     if(pr[i]>cost[tm][i]+pr[tm])

                     {

                         node[i]=map[tm][i]+node[tm];

                         pr[i]=cost[tm][i]+pr[tm];

                     }

                 }

                 if (Min>node[i])

                 {

                     M=pr[i];

                     Min=node[i];

                     m=i;

                 }

                 else if (Min==node[i])

                 {

                     if(M>pr[i])

                     {

                         M=pr[i];

                         Min=node[i];

                         m=i;

                     }

                 }

             }

         vis[m]=;

         tm=m;

     }

 }

 int main ()

 {

     int a,b,d,p,m;

     while(scanf("%d%d",&n,&m),n||m)

     {

         set();

         while (m--)

         {

             scanf("%d%d%d%d",&a,&b,&d,&p);

             if (map[a][b]>d)

             {

                 cost[a][b]=cost[b][a]=p;

                 map[a][b]=map[b][a]=d;

             }

             else if (map[a][b]==d)

             {

                 if (cost[a][b]>p)

                     cost[a][b]=cost[b][a]=p;

             }

         }

         scanf("%d%d",&a,&b);

         dijkstra(a);

         printf ("%d %d\n",node[b],pr[b]);

     }

 }

一种简单明了的代码。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int INF=;

 int Map[][],Min,Mmin,n,cost[][],node[],vis[];

 int pr[],tm;

 void sett()

 {

     for (int i=; i<=n; i++)

     {

         node[i]=INF;

         vis[i]=;

         pr[i]=INF;

         for (int j=; j<=n; j++)

         {

             Map[i][j]=INF;

             cost[i][j]=INF;

         }

     }

 }

 int dijkstra()

 {

     for (int i=; i<=n; i++)

     {

         Min=INF;

         Mmin=INF;

         for (int j=; j<=n; j++)

         {

             if (!vis[j])

             {

                 if (Min>node[j])

                 {

                     Min=node[j];

                     Mmin=pr[j];

                     tm=j;

                 }

                 else if (Min==node[j])

                 {

                     if (Mmin>pr[j])

                     {

                         Mmin=pr[j];

                         tm=j;

                     }

                 }

             }

         }

         vis[tm]=;

         for (int j=; j<=n; j++)

             if (!vis[j])

             {

                 if (node[j]>Map[tm][j]+node[tm])

                 {

                     node[j]=Map[tm][j]+node[tm];

                     pr[j]=cost[tm][j]+pr[tm];

                 }

                 else if (node[j]==Map[tm][j]+node[tm])

                 {

                     if (pr[j]>cost[tm][j]+pr[tm])

                     {

                         node[j]=Map[tm][j]+node[tm];

                         pr[j]=cost[tm][j]+pr[tm];

                     }

                 }

             }

     }

 }

 int main ()

 {

     int m,a,b,d,p,s,t;

     while (~scanf("%d%d",&n,&m))

     {

         if (n==&&m==)

             break;

         sett();

         for (int i=; i<=m; i++)

         {

             scanf("%d%d%d%d",&a,&b,&d,&p);

             if (Map[a][b]>d)

             {

                 Map[a][b]=Map[b][a]=d;

                 cost[a][b]=cost[b][a]=p;

             }

             else if (Map[a][b]==d)

             {

                 if (cost[a][b]>p)

                     cost[a][b]=cost[b][a]=p;

             }

         }

         scanf("%d%d",&s,&t);

         node[s]=;

         pr[s]=;

         dijkstra();

         printf ("%d %d\n",node[t],pr[t]);

     }

 }

巴特西

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

最新文章

热门文章