HDU 2680（最短路）（多个起始点）

这道题也是死命TLE。。

http://acm.hdu.edu.cn/showproblem.php?pid=2680

 1 /*
 2 使用pair代替结构
 3 */
 4 
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <queue>
 8 #include <vector>
 9 using namespace std;
10 const int Ni = 1010;
11 const int INF = 0x3f3f3f3f;
12 
13 typedef pair<int,int> pa;
14 
15 int dis[Ni],n;//dis使用1-n的部分
16 
17 vector<pair<int,int> > eg[Ni];
18 
19 void Dijkstra(int s)
20 {
21           int i,j;
22           for(i=1;i<=n;i++)//要到n
23                     dis[i] = INF;
24           priority_queue<pa> q;  //优先级队列：小顶堆
25           dis[s] = 0;
26           q.push(make_pair(s,dis[s]));
27 
28           while(!q.empty())
29           {
30                     pa x = q.top();
31                     q.pop();
32                     int w = x.first;
33                     for(j = 0;j<eg[w].size();j++)//遍历x的所有邻接点
34                     {
35                               pa y = eg[w][j];//y是x的邻接点
36                               int u = y.first;
37                               if(dis[u]>x.second+y.second)
38                               {
39                                         dis[u] = x.second+y.second;
40                                         q.push(make_pair(u,dis[u]));
41                               }
42                     }
43           }
44 
45 }
46 
47 
48 int main()
49 {
50           int m,a,b,y,d,min;//关系个数
51           while(cin>>n>>m>>y)
52           {
53                     for(int i = 0;i<=n;i++)
54                               eg[i].clear();//初始化
55                     while(m--)
56                     {
57                               cin>>a>>b>>d;
58                               eg[b].push_back(make_pair(a,d));
59                     }
60 
61                     Dijkstra(y);
62 
63                     int t,x;
64                     min = INF;
65                     cin>>t;
66                     while(t--)
67                     {
68                               cin>>x;
69                               if(dis[x]<min)
70                                         min = dis[x];
71                     }
72                     if(min!=INF)
73                               cout<<min<<endl;
74                     else
75                               cout<<"-1
";
76           }
77 
78           return 0;
79 }

已ac，514MS

思路1：加辅助点

  1 #include <cstdio>
  2 using namespace std;
  3 const int L = 1010;
  4 const int INF = 1<<27;
  5 
  6 int map[L][L];
  7 int vis[L];
  8 int dis[L];
  9 
 10 int n,m;
 11 
 12 void Dijkstra()
 13 {
 14           int i,j,k;
 15           int min;
 16           for(i = 0;i<=n;i++)
 17           {
 18                     dis[i] = map[0][i];
 19                     vis[i] = 0;
 20           }
 21 
 22           vis[0] = 1;
 23           dis[0] = 0;
 24 
 25           for(i = 0;i<=n;i++)
 26           {
 27                     min = INF;
 28                     for(j = 0;j<=n;j++)
 29                     {
 30                               if(dis[j]<min && !vis[j])
 31                               {
 32                                         k = j;
 33                                         min = dis[j];
 34                               }
 35                     }
 36 
 37                     vis[k] = 1;
 38 
 39                     for(j = 0;j<=n;j++)
 40                     {
 41                               if(dis[j] > min+map[k][j] && !vis[j])
 42                               {
 43                                         dis[j] = min+map[k][j];
 44                               }
 45                     }
 46           }
 47 }
 48 
 49 void init()
 50 {
 51           int i,j;
 52           for(i = 0;i<=n;i++)
 53           {
 54                     map[i][i] = 0;
 55                     for(j = i+1;j<=n;j++)
 56                     {
 57                               map[i][j] = map[j][i] = INF;
 58                     }
 59           }
 60 
 61           while(m--)
 62           {
 63                     int a,b,w;
 64                     scanf("%d%d%d",&a,&b,&w);
 65                     if(w<map[a][b])//可能有同两点，但不同weight
 66                     {
 67                               map[a][b] = w;
 68                     }
 69           }
 70 }
 71 
 72 
 73 int main()
 74 {
 75           int y;
 76           while(~scanf("%d%d%d",&n,&m,&y))
 77           {
 78                     int r,min=INF;
 79 
 80                     init();
 81 
 82                     scanf("%d",&r);
 83                     while(r--)
 84                     {
 85                               int a;
 86                               scanf("%d",&a);
 87                               map[0][a] = 0;
 88                     }
 89 
 90                     Dijkstra();
 91 
 92                     if(dis[y]!=INF)
 93                               printf("%d
",dis[y]);
 94                     else
 95                               printf("-1
");
 96 
 97           }
 98 
 99           return 0;
100 }

思路2：反向图

  1 #include <cstdio>
  2 using namespace std;
  3 const int L = 1010;
  4 const int INF = 1<<27;
  5 
  6 int map[L][L];
  7 int vis[L];
  8 int dis[L];
  9 
 10 int n,m;
 11 
 12 void Dijkstra(int s)
 13 {
 14           int i,j,k;
 15           int min;
 16           for(i = 0;i<=n;i++)
 17           {
 18                     dis[i] = map[s][i];
 19                     vis[i] = 0;
 20           }
 21 
 22           vis[s] = 1;
 23           dis[s] = 0;
 24 
 25           for(i = 0;i<=n;i++)
 26           {
 27                     min = INF;
 28                     for(j = 0;j<=n;j++)
 29                     {
 30                               if(dis[j]<min && !vis[j])
 31                               {
 32                                         k = j;
 33                                         min = dis[j];
 34                               }
 35                     }
 36 
 37                     vis[k] = 1;
 38 
 39                     for(j = 0;j<=n;j++)
 40                     {
 41                               if(dis[j] > min+map[k][j] && !vis[j])
 42                               {
 43                                         dis[j] = min+map[k][j];
 44                               }
 45                     }
 46           }
 47 }
 48 
 49 void init()
 50 {
 51           int i,j;
 52           for(i = 0;i<=n;i++)
 53           {
 54                     map[i][i] = 0;
 55                     for(j = i+1;j<=n;j++)
 56                     {
 57                               map[i][j] = map[j][i] = INF;
 58                     }
 59           }
 60 
 61           while(m--)
 62           {
 63                     int a,b,w;
 64                     scanf("%d%d%d",&a,&b,&w);
 65                     if(w<map[b][a])//可能有同两点，但不同weight
 66                     {
 67                               map[b][a] = w;
 68                     }
 69           }
 70 }
 71 
 72 
 73 int main()
 74 {
 75           int y;
 76           while(~scanf("%d%d%d",&n,&m,&y))
 77           {
 78                     int r,min=INF;
 79 
 80                     init();
 81 
 82                     Dijkstra(y);
 83 
 84                     scanf("%d",&r);
 85                     while(r--)
 86                     {
 87                               int a;
 88                               scanf("%d",&a);
 89                               if(dis[a]<min)
 90                                         min = dis[a];
 91                     }
 92 
 93                     if(min!=INF)
 94                               printf("%d
",min);
 95                     else
 96                               printf("-1
");
 97 
 98           }
 99 
100           return 0;
101 }

http://blog.csdn.net/niushuai666/article/details/6794343

这两个思路很值得学习，而且他的两个方法都比我快