正文

The Shortest Path in Nya Graph---hdu4725（spfa+扩点建图）

IP云
IP云V管理员/4 阅读
09/16
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4725

 有n个点，每个点都有一个层l[i]，相邻层的边有一条无向带权边，权值为都为C，另外还有m条边，每条边对应的u v w 

最后求1到n的最小权值和是多少；

如果直接建图的话会TLE；这里把层数扩展为点n+1----n+n；然后在连接各种关系对应的图，最后用spfa求最短路即可，注意扩点之后点的个数；

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
typedef long long LL;
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
#define N 200005using namespace std;struct node
{
int v, w, Next;
}G[N*];int n, m, c, dist[N], vis[N], l[N], v[N];int Head[N], cnt;
void Add(int u, int v, int w)
{
G[cnt].v = v;
G[cnt].w = w;
G[cnt].Next = Head[u];
Head[u] = cnt++;
}int spfa()
{
for(int i=; i<=n*+; i++)
dist[i] = INF;
met(vis, );
queue<int>Q;
Q.push();
vis[] = ;
dist[] = ;
while(!Q.empty())
{
int p = Q.front();Q.pop();
vis[p] = ;
for(int i=Head[p]; i!=-; i=G[i].Next)
{
int q = G[i].v;
if(dist[q] > dist[p]+G[i].w)
{
dist[q] = dist[p]+G[i].w;
if(!vis[q])
{
vis[q] = ;
Q.push(q);
}
}
}
}
return dist[n];
}int main()
{
int T, t = ;
scanf("%d", &T);
while(T--)
{
met(Head, -);
met(v, );
cnt = ; scanf("%d %d %d", &n, &m, &c); for(int i=; i<=n; i++)
{
scanf("%d", &l[i]);
v[l[i]] = ;
} for(int i=; i<n; i++)
{
if(v[i] && v[i+])
{
Add(n+i, n+i+, c);///层与层之间连边；
Add(n+i+, n+i, c);
}
}
for(int i=; i<=n; i++)
{
Add(n+l[i], i, );///当前点与它所在的层连边，边为0；
if(l[i]!=) Add(i, n+l[i]-, c);///点和层间进行连边；
if(l[i]!=n) Add(i, n+l[i]+, 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);
}
int ans = spfa();
if(ans == INF) ans = -;
printf("Case #%d: %d\n", t++, ans);
}
return ;
}