描述 Description
This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this paragraph, just move on.
The Nya graph is an undirected graph with “layers”. Each node in the graph belongs to a layer, there are N nodes in total.
You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.
输入格式 InputFormat
The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has three numbers N, M (0 <= N, M <= 105) and C(1 <= C <= 103), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers li (1 <= li <= N), which is the layer of ith node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 104), which means there is an extra edge, connecting a pair of node u and v, with cost w.
输出格式 OutputFormat
For test case X, output “Case #X:” first, then output the minimum cost moving from node 1 to node N.
If there are no solutions, output -1.
样例输入 SampleInput
2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3
3 3 3
1 3 2
1 2 2
2 3 2
1 3 4
样例输出 SampleOutput
Case #1: 2
Case #2: 3
来源 Source
2013 ACM/ICPC Asia Regional Online —— Warmup2
代码 Code
建图略麻烦。将每一层都视作新的点，层与层上的点连边，层上的点与相邻层连边，且若相邻层有点则层与层连边。然后 spfa 就好了。
推荐 STL 的 deque 双向队列，这样写 slf 优化就不用纠结头溢出。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=200005;
struct edge
{
int to,next,val;
}e[10*maxn];
int head[maxn],dis[maxn],a[maxn];
bool used[maxn],b[maxn];
int i,j,t,n,m,l,r,k,z,y,x,c,cnt,ans;
deque <int> q;
inline void read(int &s)
{
s=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
}
inline void init()
{
int i,j,t;
memset(head,0,sizeof(head));
memset(b,false,sizeof(b));
memset(used,false,sizeof(used));
for (i=1;i<=n+n;i++) dis[i]=inf;
}
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
int spfa()
{
int i,j,u,v,w;
while (!q.empty()) q.pop_front();
dis[1]=0;used[1]=true;q.push_back(1);
while (!q.empty())
{
u=q.front();q.pop_front();
used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;
w=e[i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty())
{
if (dis[v]>dis[q.front()]) q.push_back(v);
else q.push_front(v);
}
else q.push_back(v);
}
}
}
}
return (dis[n]);
}
int main()
{
read(t);int test=0;
while (t--)
{
read(n);read(m);read(c);
init();
cnt=0;
for (i=1;i<=n;i++) read(x),a[i]=x,b[x]=true;
for (i=1;i<n;i++) if (b[i] && b[i+1])
{
ins(n+i,n+i+1,c);
ins(n+i+1,n+i,c);
}
for (i=1;i<=n;i++)
{
ins(n+a[i],i,0);
if (a[i]>1) ins(i,n+a[i]-1,c);
if (a[i]<n) ins(i,n+a[i]+1,c);
}
for (i=1;i<=m;i++)
{
read(x);read(y);read(z);
ins(x,y,z);
ins(y,x,z);
}
ans=spfa();
printf("Case #%d:",++test);
if (ans<inf) printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}