最短テンプレート(Dijkstra&Dijkstraアルゴリズム+スタック最適化&bellman_ford&単一ソース最短SPFA)

いくつかの違いと連絡についてhttp://blog.csdn.net/u014665013/article/details/51244615
d.各グループの最初の行は3つの整数T、SとDで、T本の道があることを示し、草の家と隣接する都市はS個(草の家からこの都市までの距離を0とする)、草の行きたい場所はD個である. 
D都市の中で草児の家の最も近い距離を求めます.
s.単一ソースの最短ルートを1回行い、距離が最も小さいものを見つければよい.
c.Dijkstraシングルソース最短

/*
Dijkstra     
       
      ，Dijkstra  ，      ，    O(n^2)
   beg         ，       ，     cost[][]
         lowcost[]，  pre[].pre[i]  beg i       ，pre[beg]=-1
        ，         
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

const int MAXN=1010;
#define typec int
const typec INF=0x3f3f3f3f;//      ，      
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg){
    for(int i=0;i<n;i++){
        lowcost[i]=INF;vis[i]=false;pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0;j<n;j++){
        int k=-1;
        int Min=INF;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[i]<Min){
                Min=lowcost[i];
                k=i;
            }
        if(k==-1)break;
        vis[k]=true;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
    }
}

int cost[MAXN][MAXN];
int lowcost[MAXN];

int main(){

    int T,S,D;
    int a,b,time;
    int city1[MAXN];
    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){
        for(int i=0;i<MAXN;++i){
            for(int j=0;j<MAXN;++j){
                cost[i][j]=INF;
            }
        }
        memset(vis,false,sizeof(vis));

        for(int i=0;i<T;++i){
            scanf("%d%d%d",&a,&b,&time);
            if(time<cost[a][b]){
                cost[a][b]=time;
                cost[b][a]=time;
            }
        }
        //0     
        for(int i=0;i<S;++i){
            scanf("%d",&city1[i]);
            cost[0][city1[i]]=0;
            cost[city1[i]][0]=0;
        }
        for(int i=0;i<D;++i){
            scanf("%d",&city2[i]);
        }

        Dijkstra(cost,lowcost,MAXN,0);
        int minTime=lowcost[city2[0]];
        for(int i=1;i<D;++i){
            if(lowcost[city2[i]]<minTime)
                minTime=lowcost[city2[i]];
        }

        printf("%d
",minTime);
    }
    return 0;
}

c 2.Dijkstraアルゴリズム+スタック最適化

/*
Dijkstra  +   
        ，   O(E log E)
        Dijkstra  
   O(E log E)
   vector<Edge>E[MAXN]        
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int MAXN=1010;
struct qnode{
    int v;
    int c;
    qnode(int _v=0,int _c=0):v(_v),c(_c){}
    bool operator <(const qnode &r)const{
        return c>r.c;
    }
};
struct Edge{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
//     1  
void Dijkstra(int n,int start){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    priority_queue<qnode>que;
    while(!que.empty())que.pop();
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty()){
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();i++){
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost){
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}

int main(){
    int T,S,D;
    int a,b,time;
    int city1[MAXN];
    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){
        for(int i=0;i<MAXN;++i){
            E[i].clear();
        }

        for(int i=0;i<T;++i){
            scanf("%d%d%d",&a,&b,&time);
            addedge(a,b,time);//      。。   ，
            addedge(b,a,time);
        }
        //0     
        for(int i=0;i<S;++i){
            scanf("%d",&city1[i]);
            addedge(0,city1[i],0);
            addedge(city1[i],0,0);
        }
        for(int i=0;i<D;++i){
            scanf("%d",&city2[i]);
        }

        Dijkstra(MAXN-1,0);
        int minTime=dist[city2[0]];
        for(int i=1;i<D;++i){
            if(dist[city2[i]]<minTime)
                minTime=dist[city2[i]];
        }

        printf("%d
",minTime);
    }
    return 0;
}

c 3.単一ソース最短bellman_fordアルゴリズム

/*
     bellman_ford  
    khtkbellman_ford  ，   O(VE)
        。
            。  true，                   
vector<Edge>E; E.clear()   ，       
     1  （ 0          ）
*/
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

const int INF=0x3f3f3f3f;
const int MAXN=1010;
int dist[MAXN];
struct Edge{
    int u,v;
    int cost;
    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
//     1  
bool bellman_ford(int start,int n){
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[start]=0;
    //   n-1 
    for(int i=1;i<n;i++){
        bool flag=false;
        for(int j=0;j<E.size();j++){
            int u=E[j].u;
            int v=E[j].v;
            int cost=E[j].cost;
            if(dist[v]>dist[u]+cost){
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)return true;//      
    }
    for(int j=0;j<E.size();j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;//     
    return true;//      
}
void addedge(int u,int v,int cost){
    E.push_back(Edge(u,v,cost));
}

int main(){
    int T,S,D;
    int a,b,time;
    int city1[MAXN];
    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){
        E.clear();

        for(int i=0;i<T;++i){
            scanf("%d%d%d",&a,&b,&time);
            addedge(a,b,time);//    。
            addedge(b,a,time);
        }
        //0     
        for(int i=0;i<S;++i){
            scanf("%d",&city1[i]);
            addedge(0,city1[i],0);
            addedge(city1[i],0,0);
        }
        for(int i=0;i<D;++i){
            scanf("%d",&city2[i]);
        }

        bellman_ford(0,MAXN-1);//MAXN-1
        int minTime=dist[city2[0]];
        for(int i=1;i<D;++i){
            if(dist[city2[i]]<minTime)
                minTime=dist[city2[i]];
        }

        printf("%d
",minTime);
    }
    return 0;
}

c 4.シングルソース最短SPFA

/*
     SPFA
     O(kE)
       ，            ，     
         
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//     
int cnt[MAXN];//         
int dist[MAXN];
bool SPFA(int start,int n){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0;i<E[u].size();i++){
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost){
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v]){
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)return false;
                    //cnt[i]       ，            
                }
            }
        }
    }
    return true;
}

int main(){
    int T,S,D;
    int a,b,time;
    int city1[MAXN];
    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){
        for(int i=0;i<MAXN;++i){
            E[i].clear();
        }

        for(int i=0;i<T;++i){
            scanf("%d%d%d",&a,&b,&time);
            addedge(a,b,time);//    。
            addedge(b,a,time);
        }
        //0     
        for(int i=0;i<S;++i){
            scanf("%d",&city1[i]);
            addedge(0,city1[i],0);
            addedge(city1[i],0,0);
        }
        for(int i=0;i<D;++i){
            scanf("%d",&city2[i]);
        }

        SPFA(0,MAXN-1);//MAXN-1
        int minTime=dist[city2[0]];
        for(int i=1;i<D;++i){
            if(dist[city2[i]]<minTime)
                minTime=dist[city2[i]];
        }

        printf("%d
",minTime);
    }
    return 0;
}

Floydの隣接表を追加します(この問題はいいですね.時間があれば見てください)
http://blog.163.com/zjut_nizhenyang/blog/static/169570029201111841938607/
Floyd 
http://www.cnblogs.com/zswbky/p/5432387.html