Hdu 4725 The Shortest Path in Nya Graph (spfa)

题目链接：

　Hdu 4725 The Shortest Path in Nya Graph

题目描述：

　　有n个点，m条边，每经过路i需要wi元。并且每一个点都有自己所在的层。一个点都乡里的层需要花费c元，问从1到N最小花费？

解题思路：

　　建图比较楠，刚开始的时候想到拆点，把一个点拆成两个，N+i表示点i所在层，对每个点对自己所在层建双向边,权值为0。然后相邻层建双向边，权值为c。对w条点之间的边，正常建。但是写出来样例都GG了。发现对于同一层的点，在我建的图中可以免费来回跑，这样好像和题意有些不符。最后把一个点拆成三个点(实际点，所在层入口，所在层出口)，实际点向出口和入口建单向边，权值为0。上一层出口向相邻层入口建单向边，权值为c。上一层入口向相邻层出口口建单向边，权值为c。然后用经过优先队列优化的spfa才能过，要不然还是GG。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include <queue>

 using namespace std;

 #define LL __int64

 const int maxn = ;

 const int INF = 1e9+;

 struct node1

 {

     int u;

     int d;

     bool operator < (const node1 &rhs)const

     {

         return d > rhs.d;

     }

 };

 struct node

 {

     int to, next, w;

 } edge[maxn*];

 int head[maxn], tot, n, c, m;

 int dist[maxn];

 void init ()

 {

     tot = ;

     memset (head, -, sizeof(head));

 }

 void add (int from, int to, int w)

 {

     edge[tot].w = w;

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 int dijkstra ()

 {

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

         dist[i] = INF;

     node1 p, q;

     priority_queue <node1> Q;

     p.d = , p.u = ;

     Q.push(p);

     dist[] = ;

     while (!Q.empty())

     {

         p = Q.top();

         Q.pop();

         if (p.u == n)

             return dist[n];

         for (int i=head[p.u]; i!=-; i=edge[i].next)

         {

             q.u = edge[i].to;

             q.d = edge[i].w;

             if (dist[q.u] > dist[p.u] + q.d)

             {

                 dist[q.u] = dist[p.u] + q.d;

                 q.d = dist[q.u];

                 Q.push (q);

             }

         }

     }

     return -;

 }

 int main ()

 {

     int T, l = ;

     scanf ("%d", &T);

     while (T --)

     {

         init ();

         scanf ("%d %d %d", &n, &m, &c);

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

         {

             int layer;

             scanf ("%d", &layer);

             add (i, *layer+n-, );

             add (*layer+n, i, );

         }

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

         {

             add (*(i-)+n-, *i+n, c);

             add (*i+n-, *(i-)+n, c);

         }

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

         {

             int u, v, w;

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

             add (u, v, w);

             add (v, u, w);

         }

         printf ("Case #%d: %d\n", ++l, dijkstra());

     }

     return ;

 }

巴特西

Hdu 4725 The Shortest Path in Nya Graph (spfa)

最新文章

热门文章