逛街

時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB

題目描述

假設(shè)渣渣灰有一個(gè)女朋友，他的女朋友要他陪著一起去公園。由于渣渣灰不喜歡運(yùn)動(dòng)，所以他想找一條最短的路到達(dá)公園。由于途中會(huì)有許多消費(fèi)點(diǎn)，而每到一個(gè)消費(fèi)點(diǎn)女朋友就要購(gòu)物，而渣渣灰比較摳，所以假如有多條最短路，則他會(huì)選擇途中消費(fèi)點(diǎn)最便宜的。給你n個(gè)點(diǎn)，m條無(wú)向邊，每條邊都有長(zhǎng)度d和花費(fèi)p，給你起點(diǎn)s，終點(diǎn)t，要求輸出起點(diǎn)到終點(diǎn)的最短距離及其花費(fèi)，如果最短距離有多條路線，則輸出花費(fèi)最少的。

輸入

輸入nm，點(diǎn)的編號(hào)是1~n然后是m行，每行4個(gè)數(shù) abdp，表示a和b之間有一條邊，且其長(zhǎng)度為d，花費(fèi)為p。最后一行是兩個(gè)數(shù) st;起點(diǎn)s，終點(diǎn)。n和m為0時(shí)輸入結(jié)束。
(1<n<=1000 0<m<100000 s != t)

輸出

輸出 一行有兩個(gè)數(shù)， 最短距離及其花費(fèi)。

樣例輸入

2 2
1 2 5 10
2 1 4 12
1 2

4 4
1 2 5 6
2 3 4 5
1 4 5 10
4 3 4 2
1 3

6 7
1 2 5 6
1 3 5 1
2 6 2 1
3 4 1 1
4 2 1 1
4 5 1 1
5 2 3 1
5 6

0 0

樣例輸出

4 12
9 11
4 3

提示

輸入樣例的空行只是為了讓大家分辨數(shù)據(jù)，輸入有沒(méi)有空行都沒(méi)關(guān)系。輸出樣例沒(méi)有空行。

題解

dijkstra算法求單源最短路簡(jiǎn)單擴(kuò)展，我們?cè)賱?chuàng)建一個(gè)value數(shù)組儲(chǔ)存花費(fèi)情況。在松弛時(shí)對(duì)value進(jìn)行改變。

松弛成功則value（s->i）=value(s->k->i)。

若最短路相等則對(duì)value值進(jìn)行比較，即value（s->i）=min(value(s->k->i),value（s->i))。

s為源點(diǎn)，i為當(dāng)前終點(diǎn)，k為中間點(diǎn)。最終輸出最短路及對(duì)應(yīng)value值即可。

#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn=1e3+10; int n,m; struct node {int ds,cs; }road[maxn][maxn]; int dis[maxn];//最短距離 bool vis[maxn]; int cost[maxn];//花費(fèi) void dijkstra(int s) {memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));memset(cost,inf,sizeof(cost));dis[s]=0;cost[s]=0;vis[s]=1;for(int i=1;i<=n;i++)dis[i]=road[s][i].ds;for(int i=1;i<=n;i++){cost[i]=road[s][i].cs;//printf("%d:%d\n",i,dis[i]);}for(int u=1;u<n;u++){int minD=inf,k=-1;for(int i=1;i<=n;i++){if(!vis[i]&&dis[i]<minD){k=i;minD=dis[i];}}vis[k]=1;for(int i=1;i<=n;i++){if(!vis[i]&&dis[k]+road[k][i].ds<dis[i]){dis[i]=dis[k]+road[k][i].ds;cost[i]=cost[k]+road[k][i].cs;}//ifif(!vis[i]&&dis[k]+road[k][i].ds==dis[i]&&cost[i]>cost[k]+road[k][i].cs){cost[i]=cost[k]+road[k][i].cs;}//if}//for} } int main() {while(scanf("%d%d",&n,&m)&&n&&m){memset(road,inf,sizeof(road));for(int i=1;i<=m;i++){int a,b,d,p;scanf("%d%d%d%d",&a,&b,&d,&p);if(d<=road[a][b].ds)//處理路徑距離{if(d==road[a][b].ds)//如果距離相等，存放最短的花費(fèi)road[a][b].cs=road[b][a].cs=min(p,road[a][b].cs);else //存放新路徑的費(fèi)用road[a][b].cs=road[b][a].cs=p;road[a][b].ds=road[b][a].ds=d;//填充路徑}}int s,t;scanf("%d%d",&s,&t);dijkstra(s);printf("%d %d\n",dis[t],cost[t]);}return 0; } #include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define Min(a,b) a>b?b:a struct Node {int adj,val; }g[1005][1005]; int dist[1005];//距離 int value[1005];//費(fèi)用 int used[1005];//標(biāo)記 int n,m,i,j; void Dijkstra(int s) {memset(dist,0x3f,sizeof(dist));memset(value,0x3f,sizeof(value));memset(used,0,sizeof(used));dist[s]=0;//從起點(diǎn)開(kāi)始value[s]=0;while(1){int k,u=-1,d[1005];int min=INF;memset(d,0,sizeof(d));for(i=1;i<=n;i++)if(used[i]==0&&dist[i]<min)//找出從起點(diǎn)到下一個(gè)最小距離的頂點(diǎn){min=dist[i];//記錄最小值u=i;//記錄下標(biāo)}if(u==-1)//判斷所有頂點(diǎn)是否都到達(dá)過(guò)return ;for(i=1,k=0;i<=n;i++)if(dist[u]==dist[i]&&used[i]==0)d[k++]=i;//從起點(diǎn)到下一個(gè)要訪問(wèn)的頂點(diǎn)的最小距離可能有多個(gè)for(i=0;i<k;i++)used[d[i]]=1;for(i=0;i<k;i++)//多個(gè)滿足的點(diǎn)分別進(jìn)行迪杰斯特拉最短路查找for(j=1;j<=n;j++)if(g[d[i]][j].adj!=INF && (dist[d[i]]+g[d[i]][j].adj)<=dist[j]){//原理與 main()函數(shù)中建立鄰接矩陣一樣if((dist[d[i]]+g[d[i]][j].adj)<dist[j])//小于的情況value[j]=value[d[i]]+g[d[i]][j].val;elsevalue[j]=Min(value[j],value[d[i]]+g[d[i]][j].val);dist[j]=dist[d[i]]+g[d[i]][j].adj;}} } int main() {while(scanf("%d%d",&n,&m) && (n||m)){int a,b,d,p;memset(g,0x3f,sizeof(g));for(i=1;i<=m;i++){scanf("%d%d%d%d",&a,&b,&d,&p);if(d<=g[a][b].adj)//處理路徑距離問(wèn)題{if(d==g[a][b].adj)//如果距離相等，則存放最少的費(fèi)用g[a][b].val=g[b][a].val=Min(p,g[a][b].val);else//否則，存放新路徑距離的費(fèi)用g[a][b].val=g[b][a].val=p;g[a][b].adj=g[b][a].adj=d;//填充路徑距離}}int s,t;scanf("%d%d",&s,&t);Dijkstra(s);printf("%d %d\n",dist[t],value[t]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的逛街 最短距离+花费的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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