题目：http://www.51nod.com/Challenge/Problem.html#!#problemId=1459
思路：使用dijkstra算法 把start作为开始节点，输出end节点即可
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int maxn = 5e2 + 5;
const int inf = 0x3f3f3f3f;
int score[maxn]; //得分和
int dis[maxn]; //花费时间和
int value[maxn]; //每个房间的分数
int vis[maxn];//标记
int map[maxn][maxn]; //图,边的权重
int n, m, start, en;void dijkstra() {for (int i = 0; i < n; i++) {dis[i] = map[start][i];}dis[start] = 0;score[start] = value[start];for (int i = 0; i < n; i++) {int min = inf;int u = start;for (int j = 0; j < n; j++)if (!vis[j] && dis[j] < min) {u = j;min = dis[j];}vis[u] = 1;for (int j = 0; j < n; j++) {if (!vis[j] && dis[j] > dis[u] + map[u][j]) {dis[j] = dis[u] + map[u][j];score[j] =score[u] + value[j];} else if (dis[j] == dis[u] + map[u][j]) {score[j] = max(score[j], score[u] + value[j]);}}}
}int main() {freopen("data.txt", "r", stdin);int x, y, z;memset(map, inf, sizeof(map));memset(score, 0, sizeof(score));memset(dis, inf, sizeof(dis));memset(vis, 0, sizeof(vis));cin >> n >> m >> start >> en;for (int i = 0; i < n; i++) {cin >> value[i];}for (int i = 0; i < m; i++) {cin >> x >> y >> z;map[x][y] = map[y][x] = z;}dijkstra();cout << dis[en] << ' ' << score[en];return 0;
}
思路来源 https://blog.csdn.net/f_zyj/article/details/52069848