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。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include <queue>
  7 using namespace std;
  8 
  9 #define LL __int64
 10 const int maxn = 310000;
 11 const int INF = 1e9+7;
 12 
 13 
 14 struct node1
 15 {
 16     int u;
 17     int d;
 18     bool operator < (const node1 &rhs)const
 19     {
 20         return d > rhs.d;
 21     }
 22 };
 23 
 24 struct node
 25 {
 26     int to, next, w;
 27 } edge[maxn*10];
 28 
 29 int head[maxn], tot, n, c, m;
 30 int dist[maxn];
 31 
 32 void init ()
 33 {
 34     tot = 0;
 35     memset (head, -1, sizeof(head));
 36 }
 37 
 38 void add (int from, int to, int w)
 39 {
 40     edge[tot].w = w;
 41     edge[tot].to = to;
 42     edge[tot].next = head[from];
 43     head[from] = tot ++;
 44 }
 45 
 46 int dijkstra ()
 47 {
 48 
 49     for (int i=0; i<=3*n; i++)
 50         dist[i] = INF;
 51 
 52 
 53     node1 p, q;
 54     priority_queue <node1> Q;
 55     p.d = 0, p.u = 1;
 56     Q.push(p);
 57     dist[1] = 0;
 58 
 59     while (!Q.empty())
 60     {
 61         p = Q.top();
 62         Q.pop();
 63         if (p.u == n)
 64             return dist[n];
 65 
 66         for (int i=head[p.u]; i!=-1; i=edge[i].next)
 67         {
 68             q.u = edge[i].to;
 69             q.d = edge[i].w;
 70 
 71             if (dist[q.u] > dist[p.u] + q.d)
 72             {
 73                 dist[q.u] = dist[p.u] + q.d;
 74                 q.d = dist[q.u];
 75                 Q.push (q);
 76             }
 77         }
 78     }
 79     return -1;
 80 }
 81 
 82 int main ()
 83 {
 84     int T, l = 0;
 85     scanf ("%d", &T);
 86     while (T --)
 87     {
 88         init ();
 89         scanf ("%d %d %d", &n, &m, &c);
 90         for (int i=1; i<=n; i++)
 91         {
 92             int layer;
 93             scanf ("%d", &layer);
 94 
 95             add (i, 2*layer+n-1, 0);
 96             add (2*layer+n, i, 0);
 97         }
 98 
 99         for (int i=2; i<=n; i++)
100         {
101             add (2*(i-1)+n-1, 2*i+n, c);
102             add (2*i+n-1, 2*(i-1)+n, c);
103         }
104 
105         for (int i=0; i<m; i++)
106         {
107             int u, v, w;
108             scanf ("%d %d %d", &u, &v, &w);
109 
110             add (u, v, w);
111             add (v, u, w);
112         }
113 
114         printf ("Case #%d: %d
", ++l, dijkstra());
115     }
116     return 0;
117 }