問(wèn)題描述：

• 小明和小芳出去鄉(xiāng)村玩，小明負(fù)責(zé)開(kāi)車(chē)，小芳來(lái)導(dǎo)航。
• 小芳將可能的道路分為大道和小道。大道比較好走，每走1公里小明會(huì)增加1的疲勞度。小道不好走，如果連續(xù)走小道，小明的疲勞值會(huì)快速增加，連續(xù)走s公里小明會(huì)增加s*s的疲勞度。
• 例如：有5個(gè)路口，1號(hào)路口到2號(hào)路口為小道，2號(hào)路口到3號(hào)路口為小道，3號(hào)路口到4號(hào)路口為大道，4號(hào)路口到5號(hào)路口為小道，相鄰路口之間的距離都是2公里。如果小明從1號(hào)路口到5號(hào)路口，則總疲勞值為(2+2)2+2+22=16+2+4=22。

• 現(xiàn)在小芳拿到了地圖，請(qǐng)幫助她規(guī)劃一個(gè)開(kāi)車(chē)的路線，使得按這個(gè)路線開(kāi)車(chē)小明的疲勞度最小。
  　　
  　　

  輸入格式：

• 輸入的第一行包含兩個(gè)整數(shù)n,m，分別表示路口的數(shù)量和道路的數(shù)量。
• 路口由1至n編號(hào)，小明需要開(kāi)車(chē)從1號(hào)路口到n號(hào)路口。
• 接下來(lái)m行描述道路，每行包含四個(gè)整數(shù)t,a,b,c，表示一條類(lèi)型為t，連接a與b兩個(gè)路口，長(zhǎng)度為c公里的雙向道路。

• 其中t為0表示大道，t為1表示小道。保證1號(hào)路口和n號(hào)路口是連通的。
  　　

  輸出格式：

• 輸出一個(gè)整數(shù)，表示最優(yōu)路線下小明的疲勞度。

樣例輸入：

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

樣例輸出：

76

樣例說(shuō)明：

• 　從1走小道到2，再走小道到3，疲勞度為52=25；然后從3走大道經(jīng)過(guò)4到達(dá)5，疲勞度為20+30=50；最后從5走小道到6，疲勞度為1。總共為76。

數(shù)據(jù)規(guī)模和約定：

• 對(duì)于30%的評(píng)測(cè)用例，1 ≤ n ≤ 8，1 ≤ m ≤ 10；
• 對(duì)于另外20%的評(píng)測(cè)用例，不存在小道；
• 對(duì)于另外20%的評(píng)測(cè)用例，所有的小道不相交；
• 對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 500，1 ≤ m ≤ 1e5，1 ≤ a, b ≤ n，t是0或1，c ≤ 105。保證答案不超過(guò)1e6。

分析：

• 典型的最短路問(wèn)題，容易想到：如果沒(méi)有小路，那么這題就是最基礎(chǔ)的最短路，直接用dijkstra求解，可以通過(guò)60%的數(shù)據(jù)
• 題目中并沒(méi)有說(shuō)明是否存在重邊 10%的數(shù)據(jù)
• 小路增加的疲勞度計(jì)算是連續(xù)走小路的路長(zhǎng)的平方，因此在多段圖中，就不能像簡(jiǎn)單的最短路問(wèn)題一樣直接存儲(chǔ)節(jié)點(diǎn)的編號(hào)和到這個(gè)點(diǎn)的最短路徑長(zhǎng)度
• 根據(jù)題目描述，在dijkstra的過(guò)程中，每個(gè)節(jié)點(diǎn)都記錄 到該節(jié)點(diǎn)的前一段走小路的長(zhǎng)度s、走小路前的疲勞值、走到這點(diǎn)的總疲勞值
• 設(shè)置從節(jié)點(diǎn)1到節(jié)點(diǎn)i的最小疲勞值為dist1[i] - 最后一段是大路；dist2[i] - 最后一段是小路
• 根據(jù)當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)路徑類(lèi)別，計(jì)算產(chǎn)生的總疲勞值，根據(jù)情況入隊(duì)（優(yōu)先隊(duì)列實(shí)現(xiàn)的dijkstra）
• 注意：c<=1e5, 計(jì)算過(guò)程中可能會(huì)出現(xiàn) c*c 這種計(jì)算，使用int會(huì)爆int ， 把整型全部設(shè)為long long 20%的數(shù)據(jù)
• 別問(wèn)我為什么知道那些百分比，說(shuō)出來(lái)都是淚

#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = 1e9+10; const LL maxn = 505; typedef pair<LL,LL> P;vector<P>mp[maxn][maxn]; LL dist1[maxn],dist2[maxn],vis1[maxn],vis2[maxn]; LL n,m,t,a,b,c; struct node {LL id,totCost,daCost,xiaoCost,s;node(){}node(LL a,LL b,LL c) {id=a;totCost=b;s=c;}node(LL a,LL b,LL c,LL d){id=a;totCost=b;s=c;daCost = d;}friend bool operator<(const node& a,const node& b){if(a.totCost!=b.totCost)return a.totCost>b.totCost;return a.s>b.s;} };priority_queue<node>priq;void init() {while(!priq.empty()) priq.pop();for(LL i=0;i<maxn;i++){dist1[i] = dist2[i] = INF;vis1[i] = vis2[i]= 0;}for(LL i=0;i<maxn;i++)for(LL j=0;j<maxn;j++)mp[i][j].clear();}void input() {cin>>n>>m;while(m--){cin>>t>>a>>b>>c;mp[a][b].push_back(P(t,c));mp[b][a].push_back(P(t,c));} }void dijkstra() {dist1[1] = dist2[1] = 0;vis2[1]=1;priq.push(node(1,0,0,0));while(!priq.empty()){node e = priq.top();priq.pop();LL now=e.id;LL totCost = e.totCost;LL daCost = e.daCost;LL s = e.s;if(s) vis2[now]=1;else vis1[now]=1;for(LL i=2;i<=n;i++){if(vis1[i]&&vis2[i]) continue;for(LL j=0;j<mp[now][i].size();j++){P xxx = mp[now][i][j];if(xxx.first){ // 這條路是小路LL len = s+xxx.second;LL cost = daCost +len*len; ///watch out!! len*len>intif(cost<=dist2[i]) {dist2[i] = cost;priq.push(node(i,cost,len,daCost));}}else { // 這條路是大路LL cost = totCost + xxx.second;if(cost<=dist1[i]){dist1[i] = cost;priq.push(node(i,cost,0,cost));}}}}} }int main() {init();input();dijkstra();cout<<min(dist1[n],dist2[n])<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/star-and-me/p/9623828.html

總結(jié)

以上是生活随笔為你收集整理的CSP 行车路线 最短路变型的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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