hdu4725The Shortest Path in Nya Graph(拆点 + 最短路dijkstra | SPFA)
题目大意：给n个点，m条无向边，边权w，为走这条路的代价。每个点属于某一层，从某层到隔壁层代价都是固定的c，求1到n最短路。题目分析：最短路。比赛的时候硬上SPFA，结果T出翔了。还是太年轻了啊。
因为每个点可以借助层的属性，到达其他点就有了其他的路径。所以有必要把每层也抽象出额外的点。因为每层的点也是不连通的，就是说如果点i和点j在同一层，并不代表他们之间距离就是0。所以对于层节点，还需要拆点。将每层的点拆成i+n和i + n + n 2个点。i+n表示进入第i层，i+n+n表示从第i层出去。建图的时候如果某点j属于第i层，那么
j--->i + n连一条权为0的边，i + n + n --->j连一条权为0的边。对于层与层之间的关系，因为层抽象出来的点只是一个中间媒介点，所以对于进入第i层的边，只可能通过i+n这个点直接从隔壁层出去，于是i+n--->i +1 + n + n连边，边权c，i + n +1 --->i + n + n连边，边权c。注意虽然第i层被抽象出了i+n和I+ n + n2个点，但他们之间不能连边，因为同一层的点距离不为0，连边了就失去了拆点的意义。
trick：n可以为0。。。
补充：其实这题原来可以不用拆点的。感谢小吉吉提供的思路：每层只用抽象出一个点即可，如果点i属于第j层，那么j+n-->i连边，边权0，表示i属于j层，从j层到i的代价为0，那么如何表示i到j层的代价呢，因为层与层直接的代价是c，i属于j层，那么i到j层的代价是0，直接可以省了，直接建边i-->j - 1,i-->j + 1，边权为c。这样可以少n个点。其实跟拆2个点本质上还是一样的，只是在3n个点的图上做了简化，经过测试，速度和拆3个点差不多，dijkstra和SPFA都可以过。
这题卡SPFA卡的比较厉害，T了n次，后来重写了一下总算过了，不过各种优化也进不了700ms，不过优先队列优化的dijkstra却比较高效了，轻松200+ms。
详情请见代码：
1：dijkstra+优先队列：
#include <iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 300005;
const int M = 10000005;
const int inf = 0x3f3f3f3f;
int m,n,c,num;
int head[N];
int dis[N];
bool flag[N];
struct nd
{
int dist,id;
bool operator< (const nd &a)const
{
return dist > a.dist;
}
}ss,st;
priority_queue<nd>lcm;
struct node
{
int to,next,w;
}g[M];
void build(int s,int e,int w)
{
g[num].to = e;
g[num].w = w;
g[num].next = head[s];
head[s] = num ++;
}
void dijkstra()
{
int i,u;
ss.dist = 0;
ss.id = 1;
dis[1] = 0;
while(!lcm.empty())
lcm.pop();
lcm.push(ss);
while(!lcm.empty())
{
ss = lcm.top();
lcm.pop();
u = ss.id;
if(flag[u])
continue;
flag[u] = true;
for(i = head[u];i != -1;i = g[i].next)
{
if(flag[g[i].to] == false && dis[g[i].to] > dis[u] + g[i].w)
{
dis[g[i].to] = dis[u] + g[i].w;
ss.dist = dis[g[i].to];
ss.id = g[i].to;
lcm.push(ss);
}
}
}
}
int main()
{
int i,a,b,t,cas = 0;
int level;
scanf("%d",&t);
while(t --)
{
scanf("%d%d%d",&n,&m,&c);
memset(head,-1,sizeof(head));
num = 0;
for(i = 1;i < n;i ++)
{
build(n + i + 1,n + n + i,c);
build(n + i,n + n + i + 1,c);
}
for(i = 1;i <= n;i ++)
{
dis[i] = dis[i + n] = dis[i + n + n] = inf;
flag[i] = flag[i + n] = flag[i + n + n] = false;
scanf("%d",&level);
build(i,n + level,0);
build(n + n + level,i,0);
}
for(i = 1;i <= m;i ++)
{
scanf("%d%d%d",&a,&b,&level);
build(a,b,level);
build(b,a,level);
}
printf("Case #%d: ",++cas);
dijkstra();
if(dis[n] == inf || n == 0)
dis[n] = -1;
printf("%d\n",dis[n]);
}
return 0;
}
//234MS 10584K
2：SPFA：
#include <iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 300005;
const int M = 10000005;
const int inf = 0x3f3f3f3f;
int m,n,c,num;
int head[N];
int dis[N];
bool flag[N];
struct nd
{
int dist,id;
bool operator< (const nd &a)const
{
return dist > a.dist;
}
}ss,st;
int que[M];
struct node
{
int to,next,w;
}g[M];
void build(int s,int e,int w)
{
g[num].to = e;
g[num].w = w;
g[num].next = head[s];
head[s] = num ++;
}
void SPFA()
{
int i;
dis[1] = 0;
flag[1] = true;
int front,rear;
front = rear = 0;
que[rear ++] = 1;
while(front != rear)
{
int u = que[front ++];
flag[u] = false;
if(front == M)
front = 0;
for(i = head[u];i != -1;i = g[i].next)
{
if(dis[g[i].to] > dis[u] + g[i].w)
{
dis[g[i].to] = dis[u] + g[i].w;
if(flag[g[i].to] == false)
{
flag[g[i].to] = true;
que[rear ++] = g[i].to;
if(rear == M)
rear = 0;
}
}
}
}
}
int main()
{
int i,a,b,t,cas = 0;
int level;
scanf("%d",&t);
while(t --)
{
scanf("%d%d%d",&n,&m,&c);
memset(head,-1,sizeof(head));
num = 0;
for(i = 1;i < n;i ++)
{
build(n + i + 1,n + n + i,c);
build(n + i,n + n + i + 1,c);
}
for(i = 1;i <= n;i ++)
{
dis[i] = dis[i + n] = dis[i + n + n] = inf;
flag[i] = flag[i + n] = flag[i + n + n] = false;
scanf("%d",&level);
build(i,n + level,0);
build(n + n + level,i,0);
}
for(i = 1;i <= m;i ++)
{
scanf("%d%d%d",&a,&b,&level);
build(a,b,level);
build(b,a,level);
}
printf("Case #%d: ",++cas);
SPFA();
if(dis[n] == inf || n == 0)
dis[n] = -1;
printf("%d\n",dis[n]);
}
return 0;
}
//906MS 13856K
//750MS 13856K
//796MS 13856K
补充：软件开发 , C++ ,
