PTA1030 Travel Plan（单源最短+花费最小）

分析：经典的题目，保证单源最短的情况下，花费最小。
遇到的问题：
（1）前两遍写都遇到了段错误的问题，如最下面的代码所示。原因可能是都调用了递归的方式来打印路径，可能堆栈溢出（调用的次数过多）。
（2）在写dfs的时候,我写通过return step来返回到达目标走的步数，实际上这样是不能返回正确的结果，而正确的写法如下AC代码所示。
（3）当两条路长度相同的时候，注意记得更新花费。

int dfs(int x,int step,int cc){
    buf[step]=x;//cout<<"x= "<<x<<" step= "<<step<<" cc= "<<cc<<endl;if(x==d &&cc==minSpend){
    memcpy(path,buf,sizeof(buf));return step;}for(int i=0;i<n;i++){
    if(!visit[i]&&mp[x][i]!=inf){
    visit[i]=1;dfs(i,step+1,cc+spend[x][i]);visit[i]=0;}}return -1;
}

AC：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 510
using namespace std;
int mp[maxn][maxn],spend[maxn][maxn];
int lowcost[maxn],lowspend[maxn],vis[maxn];
int n,m,s,d;
int minSpend,minDis,visit[maxn],ss;
int buf[maxn],path[maxn];
void dijkstra(int s){
    for(int i=0;i<n;i++){
    lowcost[i]=mp[s][i];lowspend[i]=spend[s][i];}vis[s]=1;lowcost[s]=0;lowspend[s]=0;for(int i=1;i<n;i++){
    int v=-1;int minn=inf;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
    lowcost[j]=lowcost[v]+mp[v][j];lowspend[j]=lowspend[v]+spend[v][j];//pre[j]=v;}if(!vis[j]&&lowcost[v]+mp[v][j]==lowcost[j]){
    if(lowspend[v]+spend[v][j]<lowspend[j]){
    lowspend[j]=lowspend[v]+spend[v][j];//pre[j]=v;}}}}
}
void dfs(int x,int step,int cc){
    buf[step]=x;//cout<<"x= "<<x<<" step= "<<step<<" cc= "<<cc<<endl;if(x==d &&cc==minSpend){
    memcpy(path,buf,sizeof(buf));ss=step;return ;}for(int i=0;i<n;i++){
    if(!visit[i]&&mp[x][i]!=inf){
    visit[i]=1;dfs(i,step+1,cc+spend[x][i]);visit[i]=0;}}
}
int main(){
    for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    mp[i][j]=inf;spend[i][j]=inf;}mp[i][i]=0;spend[i][i]=0;}cin>>n>>m>>s>>d;for(int i=0;i<m;i++){
    int x,y,di,co;cin>>x>>y>>di>>co;if(mp[x][y]>di){
    mp[x][y]=mp[y][x]=di;}spend[x][y]=spend[y][x]=co;}dijkstra(s);minDis=lowcost[d];minSpend=lowspend[d];visit[s]=1;dfs(s,0,0);for(int i=0;i<=ss;i++){
    cout<<path[i]<<" ";}cout<<minDis<<" "<<minSpend<<endl;return 0;
}

分析：段错误。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 510
using namespace std;
int mp[maxn][maxn],spend[maxn][maxn];
int lowcost[maxn],lowspend[maxn],vis[maxn];
int n,m,s,d;
int pre[maxn];
void dijkstra(int s){
    for(int i=0;i<n;i++){
    lowcost[i]=mp[s][i];lowspend[i]=spend[s][i];}vis[s]=1;lowcost[s]=0;lowspend[s]=0;for(int i=1;i<n;i++){
    int v=-1;int minn=inf;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
    lowcost[j]=lowcost[v]+mp[v][j];lowspend[j]=lowspend[v]+spend[v][j];pre[j]=v;}if(!vis[j]&&lowcost[v]+mp[v][j]==lowcost[j]){
    if(lowspend[v]+spend[v][j]<lowspend[j]){
    lowspend[j]=lowspend[v]+spend[v][j];pre[j]=v;}}}}
}int main(){
    for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    mp[i][j]=inf;spend[i][j]=inf;}mp[i][i]=0;spend[i][i]=0;}cin>>n>>m>>s>>d;for(int i=0;i<m;i++){
    int x,y,di,co;cin>>x>>y>>di>>co;if(mp[x][y]>di){
    mp[x][y]=mp[y][x]=di;}spend[x][y]=spend[y][x]=co;}dijkstra(s);int minDis=lowcost[d];int minSpend=lowspend[d];int b[maxn],pos=0;pre[s]=-1;while(pre[d]!=-1){
    b[pos++]=d;d=pre[d];}cout<<s<<" ";for(int i=pos-1;i>=0;i--){
    cout<<b[i]<<" ";}cout<<minDis<<" "<<minSpend<<endl;return 0;
}

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 510
using namespace std;
int mp[maxn][maxn],spend[maxn][maxn];
int lowcost[maxn],lowspend[maxn],vis[maxn];
int n,m,s,d;
int pre[maxn];
void dijkstra(int s){
    for(int i=0;i<n;i++){
    lowcost[i]=mp[s][i];lowspend[i]=spend[s][i];}vis[s]=1;lowcost[s]=0;lowspend[s]=0;for(int i=1;i<n;i++){
    int v=-1;int minn=inf;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<n;j++){
    if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
    lowcost[j]=lowcost[v]+mp[v][j];lowspend[j]=lowspend[v]+spend[v][j];pre[j]=v;}if(!vis[j]&&lowcost[v]+mp[v][j]==lowcost[j]){
    if(lowspend[v]+spend[v][j]<lowspend[j]){
    lowspend[j]=lowspend[v]+spend[v][j];pre[j]=v;}}}}
}
void print(int x){
    if(x==-1) {
    return ;}print(pre[x]);cout<<x<<" ";
}
int main(){
    for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    mp[i][j]=inf;spend[i][j]=inf;}mp[i][i]=0;spend[i][i]=0;}cin>>n>>m>>s>>d;for(int i=0;i<m;i++){
    int x,y,di,co;cin>>x>>y>>di>>co;if(mp[x][y]>di){
    mp[x][y]=mp[y][x]=di;}spend[x][y]=spend[y][x]=co;}dijkstra(s);int minDis=lowcost[d];int minSpend=lowspend[d];//cout<<ans;pre[s]=-1;print(pre[d]);cout<<d<<" ";cout<<minDis<<" "<<minSpend<<endl;return 0;
}