1030 Travel Plan

part 5, 5.0

题意理解

• 给出城市数量N，城市之间的路线M条，开始城市S，结束城市D，然后依次M条City1 City2 Distance Cost，给出最短路径(相同最短路径下最短时间)，路径，和所花费的时间

INPUT

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

OUTPUT

0 2 3 3 40

自己解法

• 基本的Dijstra算法套路

#include <iostream>
using namespace std;
const int inf = 99999999;
int dis[510], cost[510], pre[510], e[510][510][2];
bool visit[510];
int N, M, S, D;void getPath(int index)
{if (index != S)getPath(pre[index]);cout << index << " ";
}int main()
{cin >> N >> M >> S >> D;int a, b, c, d;fill(e[0][0], e[0][0] + 510 * 510 * 2, inf);for (int i = 0; i < M; i++){cin >> a >> b >> c >> d;e[a][b][0] = e[b][a][0] = c;e[a][b][1] = e[b][a][1] = d;}fill(dis, dis + 510, inf);fill(cost, cost + 510, inf);dis[S] = 0;cost[S] = 0;for (int i = 0; i < N; i++){int min = -1, mindis = inf;for (int j = 0; j < N; j++)if (dis[j] < mindis && visit[j] == false){min = j;mindis = dis[j];}if (min == -1)break;visit[min] = true;for (int j = 0; j < N; j++)if (visit[j] == false && e[min][j][0] != inf){if (dis[j] > dis[min] + e[min][j][0]){dis[j] = dis[min] + e[min][j][0];cost[j] = cost[min] + e[min][j][1];pre[j] = min;}else if (dis[j] == dis[min] + e[min][j][0])if (cost[j] > cost[min] + e[min][j][1]){cost[j] = cost[min] + e[min][j][1];pre[j] = min;}}}getPath(D);cout << dis[D] << " " << cost[D] << endl;system("pause");return 0;
}

大神解法

• 柳神
• 柳神每次写相同的算法好像会写不同的套路

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, s, d;
int e[510][510], dis[510], cost[510][510];
vector<int> pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v) {temppath.push_back(v);if(v == s) {int tempcost = 0;for(int i = temppath.size() - 1; i > 0; i--) {int id = temppath[i], nextid = temppath[i-1];tempcost += cost[id][nextid];}if(tempcost < mincost) {mincost = tempcost;path = temppath;}temppath.pop_back();return ;}for(int i = 0; i < pre[v].size(); i++)dfs(pre[v][i]);temppath.pop_back();
}
int main() {fill(e[0], e[0] + 510 * 510, inf);fill(dis, dis + 510, inf);scanf("%d%d%d%d", &n, &m, &s, &d);for(int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);scanf("%d", &e[a][b]);e[b][a] = e[a][b];scanf("%d", &cost[a][b]);cost[b][a] = cost[a][b];}pre[s].push_back(s);dis[s] = 0;for(int i = 0; i < n; i++) {int u = -1, minn = inf;for(int j = 0; j < n; j++) {if(visit[j] == false && dis[j] < minn) {u = j;minn = dis[j];}}if(u == -1) break;visit[u] = true;for(int v = 0; v < n; v++) {if(visit[v] == false && e[u][v] != inf) {if(dis[v] > dis[u] + e[u][v]) {dis[v] = dis[u] + e[u][v];pre[v].clear();pre[v].push_back(u);} else if(dis[v] == dis[u] + e[u][v]) {pre[v].push_back(u);}}}}dfs(d);for(int i = path.size() - 1; i >= 0; i--)printf("%d ", path[i]);printf("%d %d", dis[d], mincost);return 0;
}