最短路算法--SPFA+嵌套map

hdu 2066

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1001;

int T,S,D;
int want[maxn];
int nex[maxn];
map<int ,map<int ,int > >mymap;

bool visited[maxn];
int dist[maxn];

void SPFA()
{
    memset(visited,false,sizeof(visited));
    for(int i=1;i<maxn;i++)
        dist[i]=INF;
    
    //起初我把与0临近的城市的dist[]值也赋成了0
    //这样做是错误的
    //因为如果与0临近的城市的dist[]值为0,那么0就不会松弛与其相邻的边,直接跳出循环
    dist[0]=0;
    queue<int >que;
    while(!que.empty())
        que.pop();
    que.push(0);

    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        visited[u]=false;

        for(map<int ,int >::iterator it=mymap[u].begin();it != mymap[u].end();++it)
        {
            int v=it->first;
            int weight=it->second;
            if(dist[v] > dist[u]+weight)
            {
                dist[v]=dist[u]+weight;
                if(!visited[v])
                {
                    que.push(v);
                    visited[v]=true;
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d%d",&T,&S,&D))
    {
        mymap.clear();
        for(int i=1;i<=T;i++)
        {
            int a,b,time;
            scanf("%d%d%d",&a,&b,&time);
            if(!mymap[a].count(b))
            {
                mymap[a][b]=time;
                mymap[b][a]=time;
            }
            else
            {
                mymap[a][b]=(mymap[a][b] > time ? time:mymap[a][b]);
                mymap[b][a]=(mymap[b][a] > time ? time:mymap[b][a]);
            }
        }
        for(int i=1;i<=S;i++)
        {
            scanf("%d",nex+i);
            mymap[0][nex[i]]=0;
        }
        for(int i=1;i<=D;i++)
            scanf("%d",want+i);
        SPFA();
        int ans=dist[want[1]];
        for(int i=2;i<=D;i++)
            ans=(dist[want[i]] < ans ? dist[want[i]]:ans);
        printf("%d
",ans);
    }
    return 0;
}