单源最短路裸题
1 #include<stdio.h>
2 #include<string.h>
3 #define min(a,b) (a)<(b)?a:b
4 #define INF 100001
5 int T,S,D,dist[1050],v[1050][1050],m,l[1050],r[1050];
6
7 void DIJKSTRA(int x){
8 int i,j,mi,minj;
9 bool visit[1050]={0};
10 for(i=1;i<=m;i++)dist[i]=v[x][i];
11 visit[x]=1;
12 for(i=1;i<m;i++){
13 mi=INF;
14 for(j=1;j<=m;j++){
15 if(!visit[j]&&dist[j]<mi){
16 mi=dist[j];
17 minj=j;
18 }
19 }
20 if(mi==INF) return;
21 visit[minj]=1;
22 for(j=0;j<=m;j++){
23 if(!visit[j]&&dist[j]>dist[minj]+v[minj][j]){
24 dist[j]=dist[minj]+v[minj][j];
25 }
26 }
27 }
28 }
29
30
31 int main(){
32 while(scanf("%d%d%d",&T,&S,&D)!=EOF){
33 int q,tm=0xFFFFFFF,i,j;
34 for(i=1;i<1050;i++){
35 for(j=1;j<1050;j++){
36 v[i][j]=INF;
37 }
38 }
39 m=-1;
40 for(q=1;q<=T;q++){
41 int a,b,va;
42 scanf("%d%d%d",&a,&b,&va);
43 v[a][b]=v[b][a]=min(va,v[a][b]);
44 if(a>m)m=a;
45 if(b>m)m=b;
46 }
47 for(q=1;q<=S;q++)scanf("%d",&l[q]);
48 for(q=1;q<=D;q++)scanf("%d",&r[q]);
49 for(i=1;i<=S;i++){
50 DIJKSTRA(l[i]);
51 for(j=1;j<=D;j++){
52 if(dist[r[j]]<tm)tm=dist[r[j]];
53 }
54 }
55 printf("%d
",tm);
56 }
57 return 0;
58 }
以前不太懂，头硬直接跑了s遍没有优化的dijkstra，每遍循环看下d个点取最优也能过，复杂度应该是O( s * (n^2) )，那么大概s不是很大，所以据说O(n^3)的floyd过不了(据说，我也不清楚)，但是这样都能过。
不过现在重新看，这个题对于初学者来说应该还是很有亮点的。
它的s个起点、d个终点可以为其建立一个源点一个汇点，这样源点有条边到每个可行起点，而每个可行终点有条边到汇点，只需要从源点到汇点跑一次单源最短路，无需遍历终点直接输出汇点的dis就是答案了。
这种题当时要是没有水过去，而是被卡了找找网上的分析，应该很有帮助吧。
1 #include<stdio.h> //基本需要的头文件
2 #include<string.h>
3 #include<queue>
4 #include<algorithm>
5 using namespace std;
6 const int INF=0x3f3f3f3f;
7
8 const int maxn=1e3+5;
9 const int maxm=1e5+5;
10
11 struct pii{
12 int dis;
13 int s;
14 bool operator < (const pii x)const{
15 return dis > x.dis;
16 }
17 pii(int a,int b):dis(a),s(b){};
18 };
19 int head[maxn],nxt[maxm<<1],val[maxm<<1],point[maxm<<1],size;
20 int dis[maxn];
21
22 void init(){
23 memset(head,-1,sizeof(head));
24 size=0;
25 }
26
27 void add(int a,int b,int v){
28 point[size]=b;
29 val[size]=v;
30 nxt[size]=head[a];
31 head[a]=size++;
32 }
33
34 void dij(int s,int t){ //传入出发点和到达点
35 int i;
36 priority_queue<pii>q;
37 q.push(pii(0,s));
38 memset(dis,0x3f,sizeof(dis));
39 dis[s]=0;
40 while(!q.empty()){
41 pii u=q.top();
42 q.pop();
43 if(u.dis>dis[u.s])continue;
44 for(i=head[u.s];~i;i=nxt[i]){
45 int j=point[i];
46 if(dis[j]>u.dis+val[i]){
47 dis[j]=u.dis+val[i];
48 q.push(pii(dis[j],j));
49 }
50 }
51 }
52 printf("%d
",dis[t]); //或去掉在主函数中输出或操作
53 }
54
55 int main(){
56 int t,s,d;
57 while(scanf("%d%d%d",&t,&s,&d)!=EOF){
58 init();
59 while(t--){
60 int a,b,v;
61 scanf("%d%d%d",&a,&b,&v);
62 add(a,b,v);
63 add(b,a,v);
64 }
65 for(int i = 1 ; i <= s ; ++ i){
66 int a;
67 scanf("%d",&a);
68 add(0,a,0);
69 }
70 for(int i = 1 ; i <= d ; ++ i){
71 int a;
72 scanf("%d",&a);
73 add(a,1001,0);
74 }
75 dij(0,1001);
76 }
77 return 0;
78 }