【题目链接】
http://poj.org/problem?id=4725
题目意思
题意说有n个节点，这些节点分布在n个平面上，两两相邻的平面直接的距离为c。而节点与节点也有m条边，距离为w。问你从节点1到n最短路。
解题思路
题意看了半天，才明白节点与面的关系。一开始觉的直接把面也当成节点来构图就可以了（面与面里的节点距离为0）。但是后来发现题目并没有说一个面就一个节点，当一个面出现多个节点时候，这些点的距离全部变成0了，这不符合题意。然后看大佬们怎么构图的。发现两种：一种还是把面当成一个节点，但是不在连面内部的节点与面的边，而直接连相邻面的节点距离为c，这样避免同面为0的情况（觉的好像不好写，没深究不知道有没有理解错）。而第二种就把一个面分为两个点，一个入面点，一个出面点。而把双向边变成单向边。（构完图最后跑遍单源最短路就可以了，但是要用优先队列优化不然会T）
总结下第二种构图方法注意点：
1.节点与对应层的入点有条单向边。（入指向节点）
2。节点与对应层的出点有条单向边。（出指向节点）
3.相邻两层都有i出指向出（i+1入，（i+1）出指向i入的两条单向边。（没节点的层并不影响结果）
4.m条节点到节点的双向边。
代码部分
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string>
#include <map>
using namespace std;
#define LL long long
#define inf 0x3f3f3f3
const int N = 1e5+5;
int n,m,c;
int dis[3*N];
int vis[3*N];
struct node
{
int i,c; ///节点编号和价值
friend bool operator < (node a,node b)
{
return a.c>b.c;
}
};
vector <node> M[3*N]; ///i~n为节点，n+1到2n为每层的出口，2n+1到3n为每层的出口
node add (int i,int c) ///转换成node类型
{
node t;
t.i = i;
t.c = c;
return t;
}
void init() ///初始化
{
for (int i = 1; i <= 3*n; i++)
{
M[i].clear();
dis[i] = inf;
vis[i] = 0;
}
for (int i = 1; i < n; i++)
{
M[2*n+i+1].push_back(add(n+i,c)); ///上一层出边到这层入边
M[n*2+i].push_back(add(n+i+1,c)); ///这层出边 到上一层入边
}
}
void Dijkstra()
{
priority_queue<node>q;
q.push(add(1,0));
dis[1] = 0;
while (!q.empty())
{
node t = q.top();
q.pop();
if (vis[t.i]) ///节点t.i松弛过
continue;
vis[t.i] = 1;
for (int i = 0; i < M[t.i].size();i++)
{
node k = M[t.i][i];
if (dis[k.i] > dis[t.i]+k.c && !vis[k.i]) ///松弛
{
dis[k.i] = dis[t.i ]+k.c;
q.push(add(k.i,dis[k.i]));
}
}
}
}
int main()
{
int T,cas = 1;
scanf("%d",&T);
while (T--)
{
scanf("%d %d %d",&n,&m,&c);
init();
for (int i = 1; i <= n; i++)
{
int k;
scanf("%d",&k);
M[n+k].push_back(add(i,0)); ///层入边到节点
M[i].push_back(add(2*n+k,0)); ///节点到层出边
}
for (int i = 0; i < m; i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
M[u].push_back(add(v,w)); ///节点与节点的边
M[v].push_back(add(u,w));
}
Dijkstra();
if (dis[n] == inf)
dis[n] = -1;
printf("Case #%d: %d\n",cas++,dis[n]);
}
return 0;
}