/*dijkstra*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 0x3f3f3f
using namespace std;
int map[1500][1500],dis[1500],vis[1500];
int t,s,d,n;
void dijkstra(int s)
{
      memset(vis, 0, sizeof(vis));
      int i,j,k,l;
      for(i = 1; i <= n;i++)
      dis[i] = map[s][i];
      vis[s] = 1;      
      for(i = 1;i < n; i++)
      {
            l = MAX;
            for( j = 1; j <= n;j++)
            if(!vis[j] && dis[j] < l)
            {
                  l = dis[j];
                  k = j;
            }
            if(l < MAX)
                  vis[k] = 1;
            else
                  break;      
            for(j = 1; j <= n; j++ )
            if( !vis[j] )
            dis[j] = min(dis[j],dis[k]+map[k][j]);      
      }
}
int main()
{
      int i,j,k,a,b,c;
      while(scanf("%d%d%d",&t, &s, &d)!=EOF)
      {
            for(i = 0;i < 1500; i++)
            for(j = 0;j < 1500; j++)
            {
                  if(i ==j)
                        map[i][j]=0;
                  else
                        map[i][j] = map[j][i] = MAX;
            }
            n = 0;
            while(t--)
            {
                  scanf("%d%d%d",&a,&b,&c);
                  if(c < map[a][b])
                        map[a][b] = map[b][a] = c;
                  n = max(max(a,b),n);
            }
            while(s--)
            {
                  scanf("%d",&a);
                  map[0][a] =map[a][0] = 0;
            }
            dijkstra(0);
            int mx = MAX;
            while(d--)
            {
                  scanf("%d",&a);
                  if(mx > dis[a])
                  mx = dis[a];
            }
            printf("%d\n", mx);
      }
      return 0;
}

/*spfa*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f
using namespace std;
struct node{
    int a,b,val,next;
};
node p[10100];
int head[1010],edgenum;
int t,s,d;
int q[200],x[200],flag;
int dis[1010],vis[1010];
void add(int u,int v,int w)
{
      node E = {u,v,w,head[u]};
      p[edgenum] = E;
      head[u] = edgenum++;
}
void spfa(int sx)
{
      memset(dis,0x3f,sizeof(dis));
      memset(vis,0,sizeof(vis));
      dis[sx] = 0;
      vis[sx] = 1;
      queue<int> q;
      q.push(sx);
      while(!q.empty())
      {
            int u = q.front(); q.pop(); vis[u] = 0;
            for(int i = head[u]; i != -1; i = p[i].next)
            {
                  int v = p[i].b;
                  if(dis[v] > dis[u]+p[i].val)
                  {
                        dis[v] = dis[u]+p[i].val;
                        if(!vis[v])
                        {
                              vis[v] = 1;
                              q.push(v);
                        }
                  }
            }
      }
                  
}
int main()
{
      int i,j,k;
      while(scanf("%d%d%d",&t, &s, &d)!=EOF)
      {
            memset(head,-1,sizeof(head));
            int a,b,tim;
            while(t--)
            {
                  scanf("%d%d%d",&a,&b,&tim);
                  add(a,b,tim);
                  add(b,a,tim);
            }
            for(i = 0; i< s; i++)
                  scanf("%d",&q[i]);
            int w = INF;
            for(i = 0; i < d; i++)
                  scanf("%d",&x[i]);
            for(i = 0; i < s; i++)
            {
                  spfa(q[i]);
                  for(j = 0; j < d;j++ )
                  {
                        if(w > dis[x[j]])
                        w = dis[x[j]];
                  }            
            }      
            printf("%d\n",w);
      }
    return 0;
}

/*floyd*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int dis[1001][1001],m,zx;
int q[1001],z[1001];
void floyd()
{
      int i,j,k;
      for(k = 0; k <= m; k++)
      for(i = 0; i <= m; i++)
      if(dis[i][k] != INF)
      {
            for(j = 0; j <= m ;j++)
            {
                  dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
      }
}
int main()
{
      int i,j,k,t,s,d,a,b,c;
      while(scanf("%d%d%d",&t,&s,&d)!=EOF)
      {
            m = 0;
            for(i = 0; i < 1001; i++)
            for(j = 0; j < 1001; j++)
            {
                  if(i == j)      dis[i][j] = 0;
                  else dis[i][j] = INF;
            }
            while(t--)
            {
                  scanf("%d%d%d",&a,&b,&c);
                  if(dis[a][b] > c)
                  dis[a][b] = dis[b][a] = c;
                  m = max(max(a,b),m);
            }
            memset(q,0,sizeof(q));
            memset(z,0,sizeof(z));
            for(i = 0; i < s;i++)
                  scanf("%d", &q[i]);      
            for(i = 0; i < d;i++)
                  scanf("%d", &z[i]);
            floyd();
            zx = INF;  
            for(i=0;i<s;i++)
            for(j=0;j<d;j++)
                zx=min(zx,dis[q[i]][z[j]]);
            printf("%d\n",zx);            
      }
      return 0;
}

版权声明：原创文章，若要转载，请与博主联系，谢谢