hdu-2680 Choose the best route---dijkstra+反向存图或者建立超级源点

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2680

题目大意：

给你一个有向图，一个起点集合，一个终点，求最短路

解题思路：

1.自己多加一个超级源点，把起点集合连接到超级源点上，然后将起点与超级源点的集合的路径长度设为0，这样就称为一个n+1个点的单源最短路算法。。。。。

2.反向图+终点的Dijkstra，然后记录最小值。

注意：重边处理

思路1：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int Map[maxn][maxn];

 int n, m, s;

 int d[maxn], v[maxn];

 void dijkstra()

 {

     memset(v, , sizeof(v));

     for(int i = ; i <= n; i++)d[i] = INF;

     d[] = ;//源点是0

     for(int i = ; i <= n; i++)//n+1个点，循环n+1次

     {

         int x = , m = INF;

         for(int j = ; j <= n; j++)if(!v[j] && d[j] < m)m = d[x = j];

         v[x] = ;

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

         {

             d[j] = min(d[j], d[x] + Map[x][j]);

         }

     }

     if(d[s] == INF)cout<<"-1"<<endl;

     else cout<<d[s]<<endl;

 }

 int main()

 {

     while(cin >> n >> m >> s)

     {

         int u, v, w;

         memset(Map, INF, sizeof(Map));

         while(m--)

         {

             scanf("%d%d%d", &u, &v, &w);

             Map[u][v] = min(Map[u][v], w);//注意重边

         }

         scanf("%d", &w);

         while(w--)

         {

             scanf("%d", &u);

             Map[][u] = ;//建立超级源点0

         }

         dijkstra();

     }

     return ;

 }

思路2：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int Map[maxn][maxn];

 int n, m, s;

 int d[maxn], v[maxn];

 void dijkstra()

 {

     memset(v, , sizeof(v));

     for(int i = ; i <= n; i++)d[i] = INF;

     d[s] = ;

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

     {

         int x = , m = INF;

         for(int j = ; j <= n; j++)if(!v[j] && d[j] < m)m = d[x = j];

         v[x] = ;

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

         {

             d[j] = min(d[j], d[x] + Map[x][j]);

         }

     }

 }

 int main()

 {

     while(cin >> n >> m >> s)

     {

         int u, v, w;

         memset(Map, INF, sizeof(Map));

         while(m--)

         {

             scanf("%d%d%d", &u, &v, &w);

             Map[v][u] = min(Map[v][u], w);//反向建图

         }

         dijkstra();

         scanf("%d", &w);

         int ans = INF;

         while(w--)

         {

             scanf("%d", &u);

             ans = min(ans, d[u]);

         }

         if(ans == INF)ans = -;

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

hdu-2680 Choose the best route---dijkstra+反向存图或者建立超级源点

最新文章

热门文章