传送门：HDU4725
题意：有n个点，每个点属于不同的层，相邻的两层之间有边权值为C（假设为第一类边），某些点之间也有边（输入）（假设为第二类边）。问从1到n的最短路
这题真真切切的坑啊。。数据量超大，很卡时间，一开始自己写T了，看了题解发现思路就不对，因为我当初理解的是每层只有一个点，然而并不是。。
题解两种做法
1）先将每层抽象成两个点，个人理解拆成两个点是因为每个点有两个作用，①当第一类边的出点，②当第一类边的入点。因为第一类边在两个不同的层当中，所以要分出点和入点。
由此，我们可以自己决定0-n这n个点为同一层当中的各个点（即第二类边端点），i+n为第i层的的出点，i+2*n为第i层的入点。
2）加边，同一层的点之间的边就按输入加就好了（注意是无向边），两层之间的边就需要点抽象思维了，假设某一层为i，则要到i+1层得话应该加的边是i+n -->i+2*n+1，同样的，i+1层到i层应该加的边是i+n+1-->i+2*n，权值都为c。
这时候层与层之间有边了，同一层的点之间也有边了，但是注意点和层还没有建立关系！设点j在i层上，则点j到对应层i的边为j-->i+n。
然后就是基本的最短路的，注意由于数据量大，数组一定要开的够大，虽然网上说dijkstra+priority_queue或者spfa都能过但这种方法我只过了dijkstra。。spfa怎么改都是TLE。。
如果我说的还是不懂，建议去看一下这位大牛的博客 点击打开链接
//461ms c++ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define MAXN 300005 #define inf 0x3f3f3f3f using namespace std; struct Edge{ int v,w; int next; }edge[10000005];//一定要开的足够大 struct node{ int v,w; friend bool operator<(node a,node b) { return a.w>b.w; } }; int n,m,c,cnt=0; int pre[MAXN],dis[MAXN],book[MAXN]; void add(int u,int v,int w) { edge[++cnt].v=v; edge[cnt].w=w; edge[cnt].next=pre[u]; pre[u]=cnt; } priority_queue<node>q; void dijkstra() { node t; while(!q.empty()) q.pop(); t.v=1; t.w=0; memset(dis,inf,sizeof(dis)); memset(book,0,sizeof(book)); dis[1]=0; q.push(t); while(!q.empty()) { t=q.top(); q.pop(); int u=t.v; if(book[u]) continue; book[u]=1; for(int i=pre[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!book[v]&&dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; t.v=v; t.w=dis[v]; q.push(t); } } } if(dis[n]==inf||n==0)//注意n=0有坑。。 printf("-1\n"); else printf("%d\n",dis[n]); } int main() { int t; scanf("%d",&t); for(int k=1;k<=t;k++) { int x,y,z,l; cnt=0; memset(pre,-1,sizeof(pre)); scanf("%d%d%d",&n,&m,&c); for(int i=1;i<n;i++) { add(i+n,i+2*n+1,c);//层与层之间建边 add(i+n+1,i+2*n,c); } for(int i=1;i<=n;i++) { scanf("%d",&l); add(i,l+n,0);//层与点之间建边 add(l+n*2,i,0); } for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z);//点与点之间建边 add(x,y,z); add(y,x,z); } printf("Case #%d: ",k); dijkstra(); } return 0; } 接下来是第二种方法：
1）依然是把层抽象成点，但是不用拆点了，将层点编号为n+1-2*n。
2）在层与层之间建边，点与相邻层建边，同一层的点之间建边，还有层与在该层上的点建边。这里要开数组保存一下层与点之间的对应关系，因为只有相邻的两个层之间都有点才能建边。
网上都说这样建图运行时间短，但是我写的和上面的时间差不多啊，甚至还慢。。
这种方法看不懂建议看一下这位大牛的博客：点击打开链接
//513ms c++ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define MAXN 100005 #define inf 0x3f3f3f3f using namespace std; struct node{ int v,w; int next; }edge[4000005]; int n,m,c,cnt=0; int pre[2*MAXN],dis[2*MAXN],book[2*MAXN]; int L[2*MAXN],lay[2*MAXN]; void add(int u,int v,int w) { edge[++cnt].v=v; edge[cnt].w=w; edge[cnt].next=pre[u]; pre[u]=cnt; } void spfa() { queue<int>q; while(!q.empty()) q.pop(); memset(dis,inf,sizeof(dis)); memset(book,0,sizeof(book)); dis[1]=0; q.push(1); book[1]=1; while(!q.empty()) { int u=q.front(); q.pop(); book[u]=0; for(int i=pre[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; if(!book[v]) { book[v]=1; q.push(v); } } } } if(dis[n]==inf||n==0) printf("-1\n"); else printf("%d\n",dis[n]); } int main() { int t; scanf("%d",&t); for(int k=1;k<=t;k++) { int x,y,z,l; cnt=0; memset(pre,-1,sizeof(pre)); memset(L,0,sizeof(L)); scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=n;i++) { scanf("%d",&lay[i]); L[lay[i]]=1; } for(int i=1;i<n;i++) { if(L[i]&&L[i+1]) { add(n+i,n+i+1,c);//层与层建边 add(n+i+1,n+i,c); } } for(int i=1;i<=n;i++)//注意这次循环和上一次循环顺序不能颠倒，不然一定会T。。也不知道为啥。。求各路大神指教。 { add(lay[i]+n,i,0);//层与点建边，注意方向和权值 if(lay[i]>1) add(i,n+lay[i]-1,c);//点与相邻层建边 if(lay[i]<n) add(i,n+lay[i]+1,c); } for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);//点与点建边 add(y,x,z); } printf("Case #%d: ",k); spfa(); } return 0; } 这题学的就是建图的思想。
