浙大数据结构：07-图6 旅游规划

这道题用Dijkstra算法即可解决。

1、条件准备

n、m、s、d，其中 n（2≤n≤500）是城市的个数，m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号

path数组存两点之间距离，value数组存两点之间费用

visit数组存是否访问过该结点，minvalue数组存到该点的费用（不一定最小，路径同长才取最小）

  #include <iostream>#include<vector>#include<string.h>#include <climits>using namespace std;#define endl '\n'int n,m,s,d;
int path[505][505];
int value[505][505];
int visit[505];
int minvalue[505];

2、主函数

初始化path为-1,表示没有路径。然后输入数据，存到path数组、value数组中

然后Dijkstra一下

 int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);memset(path,-1,sizeof(path));cin>>n>>m>>s>>d;for(int i=0;i<m;i++){int a,b,p,v;cin>>a>>b>>p>>v;path[a][b]=path[b][a]=p;value[a][b]=value[b][a]=v;}Dijkstra();return 0;}

3、Dijkstra

mindist数组是存到该点的最短距离的，初始s距离为0

然后遍历n遍，保证每个点都visit，minval存未访问的结点到s的最短距离，cur存是哪个结点。

第一重for循环能找到上述索要的，标记最短为1，再访问每个结点，看看从这个点到该节点的距离是否比mindist小，小的话更新mindist和minvalue

注意如果距离相等时，要比较minvalue，并更新minvalue

最后输出终点的mindist和minvalue

void Dijkstra()
{vector<int> mindist(n+5,INT_MAX);mindist[s]=0;for(int i=0;i<n;i++){int minval=INT_MAX;int cur=-1;for(int v=0;v<n;v++)if(!visit[v]&&mindist[v]<minval){minval=mindist[v];cur=v;}visit[cur]=1;for(int v=0;v<n;v++){ if(!visit[v]&&path[cur][v]>=0&&mindist[cur]+path[cur][v]<=mindist[v]){ if(mindist[cur]+path[cur][v]==mindist[v]){ if(minvalue[cur]+value[cur][v]<minvalue[v])minvalue[v]=minvalue[cur]+value[cur][v];}else  {mindist[v]=mindist[cur]+path[cur][v];minvalue[v]=minvalue[cur]+value[cur][v];}}}}cout<<mindist[d]<<' '<<minvalue[d];
}

4、总结

这道题并不难，第一次写dijkstra也用不了多长时间就能写出来。

完整代码如下：

  #include <iostream>#include<vector>#include<string.h>#include <climits>using namespace std;#define endl '\n'int n,m,s,d;
int path[505][505];
int value[505][505];
int visit[505];
int minvalue[505];void Dijkstra()
{vector<int> mindist(n+5,INT_MAX);mindist[s]=0;for(int i=0;i<n;i++){int minval=INT_MAX;int cur=-1;for(int v=0;v<n;v++)if(!visit[v]&&mindist[v]<minval){minval=mindist[v];cur=v;}visit[cur]=1;for(int v=0;v<n;v++){ if(!visit[v]&&path[cur][v]>=0&&mindist[cur]+path[cur][v]<=mindist[v]){ if(mindist[cur]+path[cur][v]==mindist[v]){ if(minvalue[cur]+value[cur][v]<minvalue[v])minvalue[v]=minvalue[cur]+value[cur][v];}else  {mindist[v]=mindist[cur]+path[cur][v];minvalue[v]=minvalue[cur]+value[cur][v];}}}}cout<<mindist[d]<<' '<<minvalue[d];
}int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);memset(path,-1,sizeof(path));cin>>n>>m>>s>>d;for(int i=0;i<m;i++){int a,b,p,v;cin>>a>>b>>p>>v;path[a][b]=path[b][a]=p;value[a][b]=value[b][a]=v;}Dijkstra();return 0;}