poj3268 Silver Cow Party（两次SPFA || 两次Dijkstra）

题目链接

题意

有向图中有n个结点，编号1~n，输入终点编号x，求其他结点到x结点来回最短路长度的最大值。

思路

最短路问题，有1000个结点，Floyd算法应该会超时，我刚开始使用的Dijkstra算法也超时，原因是因为我使用一个循环遍历结点1~n，每次遍历我都使用两次Dijkstra求i到x和x到i的最短路，时间复杂度太高。降低时间复杂度的方法是先在原矩阵的基础上使用dijkstra求结点x到其余各点的最短路径，然后将矩阵转置，在转置矩阵的基础上使用dijkstra求结点x到其余各点的最短路径，这就相当于在原矩阵上求其余各点到x的最短路径，将两次得到的最短路径的值相加取最大值即可。这题也可以使用SPFA算法解决。

代码

SPFA算法：

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 #include <vector>

 using namespace std;

 struct Edge

 {

     int s, e, dist;

     Edge() {}

     Edge(int s, int e, int d) :s(s), e(e), dist(d) {}

 };

 const int INF = 0x3f3f3f;

 const int N =  + ;

 vector<Edge> v[N];

 int dist[N];

 int visit[N];

 int n, m, x;

 int spfa(int s, int e)    //返回从结点s到结点e的最短路

 {

     queue<int> q;

     memset(visit, , sizeof(visit));

     memset(dist, INF, sizeof(dist));

     q.push(s);

     visit[s] = ;

     dist[s] = ;

     while (!q.empty())

     {

         int s = q.front();

         q.pop();

         visit[s] = ;

         for (int i = ; i < v[s].size(); i++)

         {

             int e = v[s][i].e;

             if (dist[e] > dist[s] + v[s][i].dist)

             {

                 dist[e] = dist[s] + v[s][i].dist;

                 if (!visit[e])

                 {

                     visit[e] = ;

                     q.push(e);

                 }

             }

         }

     }

     return dist[e];

 }

 int main()

 {

     //freopen("poj3268.txt", "r", stdin);

     while (scanf("%d%d%d", &n, &m, &x) == )

     {

         int a, b, d;

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

         {

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

             v[a].push_back(Edge(a, b, d));

         }

         int ans = -;

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

         {

             if (i != x)

             {

                 int dist1 = spfa(i, x);

                 int dist2 = spfa(x, i);

                 ans = max(ans, dist1 + dist2);

             }

         }

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

     }

     return ;

 }

Dijkstra算法：

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF = 0x3f3f3f;

 const int N =  + ;

 int map[N][N];

 int dist[N], reverse_dist[N];    //记录x到其余各点的最短路径，和其余各点到x的最短路径

 int visit[N];

 int n, m, x;

 void dijkstra(int s)

 {

     memset(visit, , sizeof(visit));

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

         dist[i] = map[s][i];

     dist[s] = ;

     visit[s] = ;

     int min_dist, now = s;

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

     {

         min_dist = INF;

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

         {

             if (!visit[j] && dist[j] < min_dist)

             {

                 min_dist = dist[j];

                 now = j;

             }

         }

         if (min_dist == INF) break;

         visit[now] = ;

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

             dist[j] = min(dist[j], dist[now] + map[now][j]);

     }

 }

 void reverse_map()    //将原矩阵转置

 {

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

     {

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

         {

             int t = map[i][j];

             map[i][j] = map[j][i];

             map[j][i] = t;

         }

     }

 }

 int main()

 {

     //freopen("poj3268.txt", "r", stdin);

     while (scanf("%d%d%d", &n, &m, &x) == )

     {

         memset(map, INF, sizeof(map));

         int a, b, d;

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

         {

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

             map[a][b] = d;

         }

         dijkstra(x);

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

             reverse_dist[i] = dist[i];

         reverse_map();

         dijkstra(x);

         int ans = -;

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

             if (i != x)

                 ans = max(ans, dist[i] + reverse_dist[i]);

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

     }

     return ;

 }

巴特西

poj3268 Silver Cow Party（两次SPFA || 两次Dijkstra）

最新文章

热门文章