1 //spfa  链表 ； 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #include<queue> 8 #include<cmath> 9 using namespace std;10 const int N=2500+5,M=6200+5;11 queue<int>Q;12 struct edge13 {14     int e,v;15     edge *next;16     edge(){} //声明成员函数 17     edge(int e1,int v1,edge *next1)//成员函数 18      {e=e1;v=v1;next=next1;}     19 } *a[N];20 void addedge (int x,int y ,int z)21 {22     a[x]=new edge(y,z,a[x]);23 }24 25 bool used[N];26 int dis[N]; 27 void SPFA(int s)28 {29    memset(dis,0x7f,sizeof(dis));30     memset(used,0,sizeof(used));31     32     used[s]=1;Q.push(s);dis[s]=0;33     while(!Q.empty())34     {35         s=Q.front();Q.pop();used[s]=0;36         for(edge *p=a[s];p;p=p->next)37         {38              if(dis[s]+p->v<dis[p->e])39             {40                 dis[p->e]=dis[s]+p->v;41                 if(!used[p->e])42                 {43                     Q.push(p->e);44                     used[p->e]=1;45                 }46             }47         }48     }49 }50 51 int main()52 {53     int n,m,Ts,Te,x,y,z;54     scanf("%d%d%d%d",&n,&m,&Ts,&Te);55     for(int i=0;i<m;i++)56     {57         scanf("%d%d%d",&x,&y,&z);58         addedge(x,y,z);      59         addedge(y,x,z);   60     }    61     SPFA(Ts);62     printf("%d\n",dis[Te]);63     return 0;64 }