Hdu-2680 Choose the best route

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2680

题目大意：

给你一个有向图，一个起点集合，一个终点，求最短路。。。。

解题思路：

1.自己多加一个超级源点，把起点集合连接到超级源点上，然后将起点与超级源点的集合的路径长度设为0，这样就称为一个n+1个点的单源最短路算法。。。。。

2.反向图+终点的Dijkstra，然后记录最小值。

思路1的代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX 0x3f3f3f3f
#define N 1010

int num, road, destination;
int map[N][N], dis[N];
bool visit[N];

void Dijkstra()
{
    int temp, k;
    memset(visit, 0, sizeof(visit));
    for(int i = 0; i <= num; ++i) //n+1个点的Dijkstra
        dis[i] = map[0][i];
	dis[0] = 0;
	visit[0] = 1;
    for(int i = 0; i <= num; ++i)
    {
        temp = MAX;
        for(int j = 0; j <= num; ++j)
            if(!visit[j] && temp > dis[j])
                temp = dis[k = j];
        if(temp == MAX) break;
        visit[k] = 1;
        for(int j = 0; j <= num; ++j)
            if(!visit[j] && dis[j] > dis[k] + map[k][j])
                dis[j] = dis[k] + map[k][j];
    }
}

int main()
{
    int x, y, cost, exp, cost1;
    while(scanf("%d%d%d", &num, &road, &destination) != EOF)
    {
        memset(map, MAX, sizeof(map));
        for(int i = 1; i <= road; ++i)
        {
            scanf("%d%d%d", &x, &y, &cost);
			if(cost < map[x][y])
            map[x][y] = cost;
        }
        scanf("%d", &exp);
        for(int i = 1; i <= exp; ++i) //巧妙之处，加超级源点
        {
            scanf("%d", &cost1);
            map[0][cost1] = 0;
        }
        Dijkstra();
        if(dis[destination] == MAX) printf("-1\n");
        else printf("%d\n", dis[destination]);
    }
    return 0;
}

思路2代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX 0x3f3f3f3f
#define N 1010

int num, road, destination;
int map[N][N], dis[N], oppo[N];
bool visit[N];

void Dijkstra(int start)
{
    int temp, k;
    memset(visit, 0, sizeof(visit));
    for(int i = 1; i <= num; ++i) 
        dis[i] = map[start][i];
	dis[start] = 0;
	visit[start] = 1;
    for(int i = 1; i <= num; ++i)
    {
        temp = MAX;
        for(int j = 1; j <= num; ++j)
            if(!visit[j] && temp > dis[j])
                temp = dis[k = j];
        if(temp == MAX) break;
        visit[k] = 1;
        for(int j = 1; j <= num; ++j)
            if(!visit[j] && dis[j] > dis[k] + map[k][j])
                dis[j] = dis[k] + map[k][j];
    }
}

int main()
{
    int x, y, cost, exp, minn;
    while(scanf("%d%d%d", &num, &road, &destination) != EOF)
    {
        memset(map, MAX, sizeof(map));
        for(int i = 1; i <= road; ++i)
        {
            scanf("%d%d%d", &x, &y, &cost);
			if(cost < map[y][x]) //巧妙之处：反向图
            map[y][x] = cost;
        }
        scanf("%d", &exp);
        for(int i = 1; i <= exp; ++i)
            scanf("%d", &oppo[i]);
        Dijkstra(destination);
		minn = MAX;
		for(int i = 1; i <= exp; ++i) //起点找到终点最小值
			if(dis[oppo[i]] < minn)
				minn = dis[oppo[i]];
        if(minn == MAX) printf("-1\n");
        else printf("%d\n", minn);
    }
    return 0;
}