題目鏈接：點擊查看

題目大意：給定n個點，在一般的基礎(chǔ)上給每個點一個維度，也就是多了一個參數(shù)表示所在的層次，現(xiàn)在已知：

X層的點可以通過增加權(quán)值C到達X-1層或X+1層中的任何一個點

給定m個已經(jīng)形成的路徑

在以上兩個條件的基礎(chǔ)上，求點1到點n的最小值。

題目分析：這個題的題意很好懂，就是圖很難建，一開始我沒有想到什么好的方法，就是先保存了每一層的點數(shù)，然后兩兩枚

舉，令相鄰兩層的所有點都建上權(quán)值為C的一條邊，確實很莽，也確實果不其然的MLE了，然后靜下心來想了一下，每兩個點都

建上邊的話，題目中點最多有1e5這么多，即使不算上那m條邊的話，最壞情況下也是到了1e10的數(shù)量級，不爆內(nèi)存才怪呢。。

想了很久無果之后，去網(wǎng)上搜了搜題解，感覺大牛們的做法真的很棒，也值得我去向他們學習，我就把他們的想法用自己的語表

達一下吧：

假設(shè)每一層也是一個點，這樣的話每一次的最壞情況就是每一層只有一個點，一共有n個點和n個層，這樣的話最壞情況下會出現(xiàn)

2*n個點，然后每個點都屬于一層，所以每個點都要和其對應(yīng)的層建邊，然后每個點在和相鄰的兩層建邊，也就是3*n條邊，最后

加上m條已經(jīng)建好的邊，那么最多只會有3*n+m條邊，最壞的情況也才4e5，比1e10小了不止一點半點，這樣的話建完圖就可以

直接套spfa或Dijkstra了。

講一講為什么可以這樣想吧：

因為每個點都屬于一個層，所以我們可以表示該層到該點的距離為0，然后因為每一層都可以以權(quán)值C到達相鄰的兩層，所以令該

點再與該層的相鄰兩層所表示的點來建邊，權(quán)值為C即可。我們可以舉個很簡單的例子：

例如，現(xiàn)在有三個點，每兩層之間花費的權(quán)值為C，那么我們需要六個點來維護這個圖，設(shè)點1，點2和點3表示的是點的本身，

點4，點5和點6表示的是第一層，第二層和第三層（先不管每一層是否有點，反正層數(shù)再多也不會比點的個數(shù)還多）。然后我們

假設(shè)點1和點2位于第1層，點3位于第2層，這樣我們建邊的時候，就有4->1(0)，4->2(0)，5->3(0)，1->5(C)，2->5(C)，3->4(C)

3->6(C)這里采用u->v(w)的形式，來表示每一條邊。怎么樣，看到這里應(yīng)該有一種豁然開朗的感覺了吧？是的，如果我們現(xiàn)在要

求點1到點3之間的距離，因為我沒有給出任何連接的邊，所以只能跨層得到連通路，也就是1->5(C)->3(0)，最短路也就是C了。

再說一下為什么要建單向邊吧，接著上面舉得例子，加入是雙向邊，那么關(guān)于點1和點2的邊為：4->1(0)，1->4(0)，4->2(0)，

2->4(0)。假如接下來我們給出一條已知的邊來連接點1和點2，設(shè)1->2(w)，那么我們現(xiàn)在來求一下點1到點2的距離，如果滿足題

意的話求出來的答案肯定是w，但是按照雙向邊來求的話會出現(xiàn)以下情況：1->4(0)->2(0)，結(jié)果就是點1到點2的最短距離為0，

這個結(jié)果肯定與正確答案相悖，而將其替換成單向邊的話，就可以得出正確結(jié)果了。

直接上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;//記得將N提前預設(shè)為兩倍大小，因為我們需要給每一層預設(shè)出位置，一開始沒注意這里，RE了一發(fā)struct Node {int w,to;Node(int TO,int W){w=W;to=TO;} };vector<Node>node[N];int d[N];bool vis[N];void spfa() {memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));d[1]=0;vis[1]=true;queue<int>q;q.push(1);while(!q.empty()){int tem=q.front();q.pop();vis[tem]=false;for(int i=0;i<node[tem].size();i++){Node temp=node[tem][i];if(d[temp.to]>d[tem]+temp.w){d[temp.to]=d[tem]+temp.w;if(!vis[temp.to]){q.push(temp.to);vis[temp.to]=true;}}}} }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0;while(w--){int n,m,c;scanf("%d%d%d",&n,&m,&c);for(int i=1;i<=2*n;i++)node[i].clear();for(int i=1;i<=n;i++){int a;scanf("%d",&a);node[a+n].push_back(Node(i,0));//建立從層到點的邊if(a>1){node[i].push_back(Node(a+n-1,c));//建立從點到上一層的邊}if(a<n){node[i].push_back(Node(a+n+1,c));//建立從點到下一層的邊}}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}spfa();//建好邊之后就可以直接跑模板了printf("Case #%d: ",++kase);if(d[n]==inf)cout<<-1<<endl;elsecout<<d[n]<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4725 The Shortest Path in Nya Graph(最短路+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。