7-3 旅游规划

一个变化的最短路径，每条路都有两个参数，长度和收费，要求先求出最短的路，如果都是最短，就求出花费最少的路径。再增加一个数组，然后在下面的优化里面稍微修改一下就可以了，大体还是没变的。

#include<stdio.h>#define INF 0x3ffffffint N,M,S,D;
int mp[505][505];
int cost[505][505];
int vis[505];
int d[505];//距离最短 
int c[505];//距离最短的前提下最便宜void Dij()
{for (int i = 0;i<N;i++) {d[i]=INF;}d[S] = 0;//自己到自己为0for (int i = 0;i<N;i++)//循环n次{int u = -1,min = INF;for (int i = 0;i<N;i++)//寻找d[]一个最小值{if (!vis[i] && d[i] < min){u = i;min = d[i];}}if (u==-1) return;vis[u] = 1;//已访问for(int v = 0;v<N;v++)//查看中转站{if (!vis[v] && mp[u][v]!=INF)//未被访问{if(d[u]+mp[u][v] < d[v])//先按照距离来{d[v] = d[u] + mp[u][v];c[v] = c[u] + cost[u][v];}else if (d[u]+mp[u][v]==d[v] && c[u] + cost[u][v]<c[v]){c[v] = c[u] + cost[u][v];}}}}
}
int main()
{scanf ("%d%d%d%d",&N,&M,&S,&D);for (int i = 0;i<N;i++)for (int j = 0;j<N;j++)mp[i][j] = INF;while (M--){int a,b,c,d;scanf ("%d%d%d%d",&a,&b,&c,&d);//最后死在了这里 这其实相当于无向图 所以值要设置两个mp[a][b] = c;mp[b][a] = c;cost[a][b] = d;cost[b][a] = d;}Dij();printf ("%d %d\n",d[D],c[D]);
}

然后要记住，这个相当于无向图，路是互通的，所以那个传入参数不要错了。而且设置最大值之类的，也不要搞混了。距离需要设，花费就不需要了，具体的理由是花费处于被动，他的修改因距离而改变，没有设置的必要。