HDU 2680-Choose the best route-最短(マルチスタートセット)

 
   

     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 
   
 
  

题目大意就是一个人坐公交车晕车，要找到时间最少的路线。

测试数据意思：
第一行三个数：n(车站的个数，n<1000)  |  m(代表车站之间所有线路的总个数)  | s(代表离朋友家最近的车站)
下面有m行:   p q t   意思是：一条从p到q的线路，花费t时间
m行之后有个数字：w (代表可以在开始时搭乘的车站)
下面w个数W1,W2....Ww就是车站的编号

多起点的最短路一种做法是变终点为起点，变起点为终点，最后更新一下最小值。

第二种做法是增加一个‘0’起点到所有起点集合距离为0，那么只需要求0到终点的距离就好。

4.AC代码：

我一样拍的是dijkstra，一种做法是优先队列+邻接表，这题其实有个可以优化的地方是，多条公交线路，那么肯定是乘坐最优的，直接邻接矩阵更新最小值就好（也是码完对比 时间发现n方的优化居然比堆耗时更低）

01 - dijkstra + 堆优化

#include 
#define INF 0x3f3f3f3f
#define maxn 20100
#define N 11111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
	int to, val;
	node(int a, int b) { to = a; val = b; }
	friend bool operator< (node a, node b)
	{
		return a.val < b.val;
	}
};
vector  mp[N];
int dis[N];
void dijkstra(int sta, int ed)
{
	fill(dis, dis + ed, INF);
	priority_queue q;
	dis[sta] = 0;
	q.push(node(sta, 0));
	while (!q.empty())
	{
		int u = q.top().to;
		q.pop();
		int sz = mp[u].size();
		for (int i = 0; i < sz; i++)
		{
			int v = mp[u][i].to;
			int val = mp[u][i].val;
			if (dis[v] > dis[u] + val)
				q.push(node(v, dis[v] = dis[u] + val));
		}
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	long _begin_time = clock();
#endif
	int n, m, s;
	while (~scanf("%d%d%d", &n, &m, &s))
	{
		for (int i = 0; i <= n; i++)
			mp[i].clear();
		for (int i = 0; i < m; i++)
		{
			int p, q, t;
			scanf("%d%d%d", &p, &q, &t);
			mp[p].push_back(node(q, t));
		//	mp[q].push_back(node(p, t));
		}
		int w;
		scanf("%d", &w);
		while (w--)
		{
			int x;
			scanf("%d", &x);
			mp[0].push_back(node(x, 0));
		}
		dijkstra(0, n + 1);
		printf("%d
", dis[s] == INF ? -1 : dis[s]);
	}
#ifndef ONLINE_JUDGE
	long _end_time = clock();
	printf("time = %ld ms.", _end_time - _begin_time);
#endif
	return 0;
}

#include 
#define INF 0x3f3f3f3f
#define maxn 11111
#define eps 1e-6
#define pi acos(-1.0)
#define e 2.718281828459
#define mod (int)1e9 + 7
using namespace std;
typedef long long ll;
int mp[maxn][maxn], vis[maxn], dis[maxn];
void init(int n)
{
  memset(vis, 0, sizeof(vis));
  memset(dis, INF, sizeof(dis));
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      if (i == j)
        mp[i][j] = 0;
      else
        mp[i][j] = INF;
}
void dijkstra(int ed, int sta)
{
  dis[sta] = 0;                 //     
  for (int i = 0; i <= ed; i++) //      
  {
    int x = sta, tmp = INF;
    for (int j = 0; j <= ed; j++)
      if (!vis[j] && dis[j] < tmp)
      {
        tmp = dis[j]; //     
        x = j;        //     
      }
    if (tmp == INF) //  
      break;
    vis[x] = 1; //      
    for (int j = 0; j <= ed; j++)
      if (dis[j] > dis[x] + mp[x][j])
        dis[j] = dis[x] + mp[x][j];
  }
}
int main()
{
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  long _begin_time = clock();
#endif
  int n, m, d;
  while (~scanf("%d%d%d", &n, &m, &d))
  {
    init(n);
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
      scanf("%d%d%d", &u, &v, &w);
      if (w < mp[u][v])
        mp[u][v] = w;
    }
    int num, pos;
    scanf("%d", &num);
    for (int i = 0; i < num; i++) //     
    {
      scanf("%d", &pos);
      mp[0][pos] = 0;
    }
    dijkstra(n, 0);
    if (dis[d] != INF)
      printf("%d
", dis[d]);
    else
      puts("-1");
  }

#ifndef ONLINE_JUDGE
  long _end_time = clock();
  printf("time = %ld ms.", _end_time - _begin_time);
#endif
  return 0;
}