poj 1511 Invitation Cards spfa 邻接矩阵

题目链接：

　　http://poj.org/problem?id=1511

题目大意：

　　这道题目比较难理解，我读了好长时间，最后还是在队友的帮助下理解了题意，大意就是，以一为起点，求从一到其他各点的最短回路总和。

解题思路：

　　解决这个题目有几个容易错的，解决了离ac就不远了^_^。

　　1：数据范围是1<=边数<=顶点数<=1000000，所以不能用邻接矩阵，要用邻接表，用vector实现时要动态申请内存。

　　2：求得是起始点到其他点的最短回路和，我们可以建两个邻接表（一个正向，一个负向邻接表），对两个表分别spfa就可以了。

　　3：数据太大，最后结果要用__int64或者long long保存。

（这是第一次写spfa，也是第一次用vector实现邻接表，在队友的帮助下一直从大早上到现在终于解决了，可以松口气去吃饭了）

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define maxn 1000005

 #define INF 2000000000

 struct Egde

 {

     int e, w;

     Egde(int e=, int w=) : e(e),w(w) {};//构造函数，初始化

 };

 bool vis[maxn];

 __int64 dist[maxn], p;

 vector< vector<Egde> >G[];

 void init ()

 {

     int i;

     for (i=; i<=p; i++)

         dist[i] = INF;

 }

 void spfa (int x, int s);

 int main ()

 {

     int t, q;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d", &p, &q);

         G[].clear();

         G[].resize(p+);

         G[].clear();

         G[].resize(p+);

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

         {

             int s, e, w;

             scanf ("%d %d %d", &s, &e, &w);

             G[][s].push_back (Egde(e, w));

             G[][e].push_back (Egde(s, w));

         }

         __int64 sum = ;

         spfa (, );

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

             sum += dist[i];

         spfa (, );

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

             sum += dist[i];

         printf ("%I64d\n", sum);

     }

     return ;

 }

 void spfa (int x, int s)

 {

     Egde pn;

     queue<Egde>que;

     memset (vis, false, sizeof(vis));

     init();

     pn.e = s, pn.w = ;

     dist[s] = ;

     que.push (pn);

     vis[pn.e] = true;

     while (!que.empty())

     {

         pn = que.front();

         que.pop();

         vis[pn.e] = false;

         int len = G[x][pn.e].size();

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

         {

             Egde p = G[x][pn.e][i];

             if (dist[p.e] > dist[pn.e] + p.w)

             {

                 dist[p.e] = dist[pn.e] + p.w;

                 if (!vis[p.e])

                 {

                     vis[p.e] = true;

                     que.push(p);

                 }

             }

         }

     }

 }

相识类型：poj2387

巴特西

poj 1511 Invitation Cards spfa 邻接矩阵

最新文章

热门文章