HOJ 2680 Choose the best route（单源最短路径dijkstra，水题）

单源最短路径dijkstra，水题
题目意思：
有位妹子，要去探望朋友。坐公交，朋友家附近只有一个公交站 s 。 妹子家附近有 w 个公交站可以选择。
每两个公交站 x 到 y 需要花费一定时间。问妹子需要最少的时间。
本题要点：
1、注意的地方： 路是单向的。
2、单源最短路径，dijkstra算法。 反向建图。求 s 点的单源最短路径即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1010, INF = 0x3f3f3f3f;
int station[MaxN], cnt;
int n, m, s;
int a[MaxN][MaxN], d[MaxN];
bool vis[MaxN];void dijkstra()
{
    for(int i = 1; i <= n; ++i)d[i] = INF;memset(vis, false, sizeof vis);d[s] = 0;for(int i = 1; i < n; ++i){
    int x = -1;for(int j = 1; j <= n; ++j){
    if(!vis[j] && (-1 == x || d[j] < d[x]))x = j;}if(-1 == x)return;vis[x] = 1;for(int y = 1; y <= n; ++y){
    d[y] = min(d[y], d[x] + a[x][y]);}}
}int main()
{
    int x, y, z;while(scanf("%d%d%d", &n, &m, &s) != EOF){
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)a[i][j] = INF;for(int i = 1; i <= n; ++i)a[i][i] = 0;for(int i = 0; i < m; ++i){
    scanf("%d%d%d", &x, &y, &z);//a[x][y] = min(a[x][y], z);a[y][x] = min(a[y][x], z);	// 反向加边}scanf("%d", &cnt);for(int i = 1; i <= cnt; ++i)scanf("%d", &station[i]);dijkstra();int ans = INF;for(int i = 1; i <= cnt; ++i){
    ans = min(ans, d[station[i]]);}if(ans == INF){
    printf("-1\n");}else{
    printf("%d\n", ans);}}return 0;
}/* 5 8 5 1 2 2 1 5 3 1 3 4 2 4 7 2 5 6 2 3 5 3 5 1 4 5 1 2 2 3 4 3 4 1 2 3 1 3 4 2 3 2 1 1 *//* 1 -1 */