题意：给出一堆双向路，求从N点到1点的最短路径，最裸的最短路径，建完边之后直接跑dij或者spfa就行
dij：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 typedef pair<int,int> pii; 8 const int INF=0x3f3f3f3f; 9 10 int head[1005],dist[1005],point[4005],val[4005],next[4005],size; 11 12 void add(int a,int b,int v){ 13 int i; 14 for(i=head[a];~i;i=next[i]){ 15 if(point[i]==b){ 16 if(val[i]>v)val[i]=v; 17 return; 18 } 19 } 20 point[size]=b; 21 val[size]=v; 22 next[size]=head[a]; 23 head[a]=size++; 24 } 25 26 struct cmp{ 27 bool operator()(pii a,pii b){ 28 return a.first>b.first; 29 } 30 }; 31 32 void dij(int s){ 33 int i; 34 priority_queue<pii,vector<pii>,cmp>q; 35 q.push(make_pair(0,s)); 36 memset(dist,-1,sizeof(dist)); 37 dist[s]=0; 38 while(!q.empty()){ 39 pii p=q.top(); 40 q.pop(); 41 if(p.first>dist[p.second])continue; 42 for(i=head[p.second];~i;i=next[i]){ 43 int j=point[i]; 44 if(dist[j]==-1||dist[j]>p.first+val[i]){ 45 dist[j]=p.first+val[i]; 46 q.push(make_pair(dist[j],j)); 47 } 48 } 49 } 50 printf("%d ",dist[1]); 51 } 52 53 int main(){ 54 int t,n; 55 while(scanf("%d%d",&t,&n)!=EOF){ 56 int i,j; 57 size=0; 58 memset(head,-1,sizeof(head)); 59 for(i=1;i<=t;i++){ 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 dij(n); 66 } 67 return 0; 68 }
spfa：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 6 int head[1005],dist[1005],next[4005],point[4005],val[4005],size; 7 bool vis[1005]; 8 9 void add(int a,int b,int v){ 10 int i; 11 for(i=head[a];~i;i=next[i]){ 12 if(point[i]==b){ 13 if(val[i]>v)val[i]=v; 14 return; 15 } 16 } 17 point[size]=b; 18 val[size]=v; 19 next[size]=head[a]; 20 head[a]=size++; 21 } 22 23 void spfa(int s,int p){ 24 memset(vis,0,sizeof(vis)); 25 memset(dist,-1,sizeof(dist)); 26 queue<int>q; 27 vis[s]=1; 28 dist[s]=0; 29 q.push(s); 30 while(!q.empty()){ 31 int i,t=q.front(); 32 vis[t]=0; 33 q.pop(); 34 for(i=head[t];~i;i=next[i]){ 35 int j=point[i]; 36 if(dist[j]==-1||dist[j]>dist[t]+val[i]){ 37 dist[j]=dist[t]+val[i]; 38 if(!vis[j]){ 39 q.push(j); 40 vis[j]=1; 41 } 42 } 43 } 44 } 45 printf("%d ",dist[p]); 46 } 47 48 int main(){ 49 int t,n; 50 while(scanf("%d%d",&t,&n)!=EOF){ 51 int i,j; 52 memset(head,-1,sizeof(head)); 53 size=0; 54 for(i=1;i<=t;i++){ 55 int a,b,v; 56 scanf("%d%d%d",&a,&b,&v); 57 add(a,b,v); 58 add(b,a,v); 59 } 60 spfa(n,1); 61 } 62 return 0; 63 }