基础：
   HDU1596

   HDU2112 

   HDU1874 

   HDU1869 

   HDU2066 

   HDU2094

   HDU2544 
稍加复杂：
HDU1217    顺练习map离散    难度1.

HDU1245    处理起点，终点    难度2.

HDU1535    2次迪杰斯特拉       难度2

HDU2170                      难度x

HDU3631                      难度x

HDU4284   BFS+floyd        难度2.

加深对k的理解：
 HDU1599（最小环）  
 ZOJ3710
判环：
 HDU1317   

暴力搜索+floyd

HDU1217

#include<cstdlib>

#include<iostream>

#include<map>

using namespace std;

int n,m,Case=;

map<string,int>q;

double Map[][],tmp;

string s,s1,s2;

int main()

{

    int i,j,k;

    bool flag;

    while(~scanf("%d",&n)){

        if(n<=) return ;

        q.clear();

        for(i=;i<=n;i++){

            cin>>s;

            q[s]=i;

        }

        cin>>m;

        for(i=;i<=n;i++)

         for(j=;j<=n;j++)

          if(i==j) Map[i][j]=;

          else Map[i][j]=;

        for(i=;i<=m;i++){

            cin>>s1>>tmp>>s2;

            Map[q[s1]][q[s2]]=tmp;

        }

        for(k=;k<=n;k++)

         for(i=;i<=n;i++)

          for(j=;j<=n;j++)

           if(Map[i][j]<Map[i][k]*Map[k][j])

            Map[i][j]=Map[i][k]*Map[k][j];

       flag=false;

       for(i=;i<=n;i++)

        if(Map[i][i]>) {flag=true;break;}

       printf("Case %d: ",++Case);

       if(flag) printf("Yes\n");

       else printf("No\n");

    }

    return ;

}

HDU1245

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

#include<cmath>

using namespace std;

const double inf=;

int n;

double Map[][],x[],y[],d;

int step[][];

int main()

{

     int i,j,k;

     while(~scanf("%d%lf",&n,&d)){

         n++;

        for(i=;i<=n;i++)

          for(j=;j<=n;j++)

          {

              Map[i][j]=inf;

              step[i][j]=inf;

          }

        for(i=;i<n;i++)

        {

            cin>>x[i]>>y[i];

            double tmp=sqrt((x[i]*x[i])+(y[i]*y[i]));

            if(tmp-7.5<=d&&tmp>7.5){//不加tmp>7.5就错了，因为会出现负数Map

                Map[][i]=tmp-7.5;

                step[][i]=;

            }

        }

        if(d>=42.5){

            Map[][n]=42.50;

            step[][n]=;

        }

        for(i=;i<n;i++)

          for(j=i+;j<n;j++)

          {

            double tmp=sqrt(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j])));

            if(tmp<=d){

                Map[i][j]=tmp;

                step[i][j]=;

                Map[j][i]=tmp;

                step[j][i]=;

            }

         }

        for(i=;i<n;i++)

        {

            double tmp=min(abs(-x[i]),abs(+x[i]));

            tmp=min(tmp,abs(-y[i]));

            tmp=min(tmp,abs(+y[i]));

            if(tmp<=d){

              Map[i][n]=tmp;

              step[i][n]=;

            }

        }

        for(k=;k<=n;k++)

         for(i=;i<=n;i++)

          for(j=;j<=n;j++)

          {

                if(Map[i][j]>Map[i][k]+Map[k][j]){

                    Map[i][j]=Map[i][k]+Map[k][j];

                    step[i][j]=step[i][k]+step[k][j];

                }

                else if(Map[i][j]==Map[i][k]+Map[k][j])

                 step[i][j]=min(step[i][j],step[i][k]+step[k][j]);

          }

         if(Map[][n]==inf) printf("can't be saved\n");

         else printf("%.2lf %d\n",Map[][n],step[][n]);

     }

    return ;

}

HDU1596

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<memory.h>

using namespace std;

double Map[][];

int main()

{

    int n,i,j,k,m,a,b;

    while(~scanf("%d",&n)){

        for(i=;i<=n;i++)

         for(j=;j<=n;j++)

          scanf("%lf",&Map[i][j]);

        for(k=;k<=n;k++)

         for(i=;i<=n;i++)

          for(j=;j<=n;j++)

            if(Map[i][j]<Map[i][k]*Map[k][j])

             Map[i][j]=Map[i][k]*Map[k][j];

        scanf("%d",&m);

        while(m--){

             scanf("%d%d",&a,&b);

             if(Map[a][b]==) printf("What a pity!\n");

             else printf("%.3lf\n",Map[a][b]);

        }

    }

    return ;

}

HDU1535

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

#include<queue>

using namespace std;

const int inf=;

const int Maxn=;

const int Maxm=;

int dis1[Maxn],Laxt1[Maxn],len1[Maxm],To1[Maxm],Next1[Maxm];

int dis2[Maxn],Laxt2[Maxn],len2[Maxm],To2[Maxm],Next2[Maxm];

int n,m,cnt1,cnt2;

queue<int>q1;

queue<int>q2;

bool w1[Maxn];

bool w2[Maxn];

void _update()

{

    dis1[]=;

    for(int i=;i<=n;i++) dis1[i]=inf;

    memset(Laxt1,,sizeof(Laxt1));

    memset(w1,,sizeof(w1));

    cnt1=;

    dis2[]=;

    for(int i=;i<=n;i++) dis2[i]=inf;

    memset(Laxt2,,sizeof(Laxt2));

    memset(w2,,sizeof(w2));

    cnt2=;

}

void _add(int u,int v,int d)

{

    Next1[++cnt1]=Laxt1[u];

    Laxt1[u]=cnt1;

    To1[cnt1]=v;

    len1[cnt1]=d;

    Next2[++cnt2]=Laxt2[v];

    Laxt2[v]=cnt2;

    To2[cnt2]=u;

    len2[cnt2]=d;

}

void _init()

{

    int i,x,y,z;

    for(i=;i<=m;i++){

        scanf("%d%d%d",&x,&y,&z);

        _add(x,y,z);

    }

}

void _dij1()

{

    q1.push();

    w1[]=true;

    while(!q1.empty()){

         int s=q1.front();

         q1.pop();

         w1[s]=false;

         for(int i=Laxt1[s];i>;i=Next1[i]){

                if(dis1[To1[i]]>dis1[s]+len1[i]){

                    dis1[To1[i]]=dis1[s]+len1[i];

                    if(!w1[To1[i]]){

                        w1[To1[i]]=true;

                        q1.push(To1[i]);

                    }

                }

         }

    }

}

void _dij2()

{

    q2.push();

    w2[]=true;

    while(!q2.empty()){

         int s=q2.front();

         q2.pop();

         w2[s]=false;

         for(int i=Laxt2[s];i>;i=Next2[i]){

                if(dis2[To2[i]]>dis2[s]+len2[i]){

                    dis2[To2[i]]=dis2[s]+len2[i];

                    if(!w2[To2[i]]){

                        w2[To2[i]]=true;

                        q2.push(To2[i]);

                    }

                }

         }

    }

}

int main()

{

    int T,i,j,k;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        _update();

        _init();

        _dij1();

        _dij2();

        int ans=;

        for(i=;i<=n;i++)

         ans+=dis1[i]+dis2[i];

        cout<<ans<<endl;

    }

    return ;

}

HDU1869

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<string>

#include<memory.h>

using namespace std;

const int inf=;

int Map[][],m,n;

int k,i,j;

int x,y,z,s,t;

int main()

{

    while(~scanf("%d%d",&n,&m)){

        for(i=;i<n;i++)

         for(j=;j<n;j++)

          if(i!=j) Map[i][j]=inf;

        for(i=;i<=m;i++){

            scanf("%d%d",&x,&y);

            Map[x][y]=;

            Map[y][x]=;

        }

        for(k=;k<n;k++)

         for(i=;i<n;i++)

          for(j=;j<n;j++)

           if(Map[i][j]>Map[i][k]+Map[k][j])

            Map[i][j]=Map[i][k]+Map[k][j];

        bool flag=true;

        for(i=;i<n;i++)

         for(j=i+;j<n;j++)

          if(Map[i][j]>) { flag=false;break;}

        if(flag) cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

    return ;

}

hdu1599

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<string>

#include<memory.h>

using namespace std;

const int inf=;

int Map[][],mp[][],m,n;

int k,i,j;

int x,y,z,s,t;

int main()

{

    while(~scanf("%d%d",&n,&m)){

        for(i=;i<=n;i++)

         for(j=;j<=n;j++)

          Map[i][j]=inf;

        for(i=;i<=m;i++){

            scanf("%d%d%d",&x,&y,&z);

            if(Map[x][y]>z) Map[x][y]=z;

            if(Map[y][x]>z) Map[y][x]=z;

        }

        for(i=;i<=n;i++)

         for(j=;j<=n;j++)

          mp[i][j]=Map[i][j];

        int  ans=inf;

        for(k=;k<=n;k++){

          for(i=;i<k;i++)

           for(j=i+;j<k;j++)

             if(mp[i][k]+mp[j][k]+Map[i][j]<ans)

              ans=mp[i][k]+mp[j][k]+Map[i][j];

          for(i=;i<=n;i++)

           for(j=;j<=n;j++)

              if(Map[i][j]>Map[i][k]+Map[k][j])

               Map[i][j]=Map[i][k]+Map[k][j];

        }

        if(ans>=inf) cout<<"It's impossible."<<endl;

        else cout<<ans<<endl;

    }

    return ;

}

HDU1874

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<string>

#include<memory.h>

using namespace std;

const int inf=;

int Map[][],m,n;

int k,i,j;

int x,y,z,s,t;

int main()

{

    while(~scanf("%d%d",&n,&m)){

        for(i=;i<n;i++)

         for(j=;j<n;j++)

          if(i!=j) Map[i][j]=inf;

        for(i=;i<=m;i++){

            scanf("%d%d%d",&x,&y,&z);

            if(Map[x][y]>z) Map[x][y]=z;

            if(Map[y][x]>z) Map[y][x]=z;

        }

        scanf("%d%d",&s,&t);

        for(k=;k<n;k++)

         for(i=;i<n;i++)

          for(j=;j<n;j++)

           if(Map[i][j]>Map[i][k]+Map[k][j])

            Map[i][j]=Map[i][k]+Map[k][j];

        if(Map[s][t]==inf) cout<<"-1"<<endl;

        else cout<<Map[s][t]<<endl;

    }

    return ;

}

hdu2094

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<memory.h>

using namespace std;

map<string,int>q;

int Map[][];

int main(){

    int n,cnt,i,k,j;

    string s1,s2;

    while(~scanf("%d",&n)){

        if(n==) return ;

        cnt=;

        q.clear();

        memset(Map,,sizeof(Map));

        for(i=;i<=n;i++){

            cin>>s1>>s2;

            if(q.find(s1)==q.end())  q[s1]=++cnt;

            if(q.find(s2)==q.end())  q[s2]=++cnt;

            Map[q[s1]][q[s2]]=;

        }

        for(k=;k<=cnt;k++)

         for(i=;i<=cnt;i++)

          for(j=;j<=cnt;j++)

          if(Map[i][k]==&&Map[k][j]==) Map[i][j]=;

        bool ok,over=false;

        for(i=;i<=cnt;i++){

           ok=true;

         for(j=;j<=cnt;j++){

             if(i==j) continue;

             if(Map[i][j]!=) ok=false;

             if(Map[j][i]==) ok=false;

         }

         if(ok) {

                printf("Yes\n");

                over=true;

                break;

         }

        }

        if(!over) printf("No\n");

    }

    return ;

}

HDU2112

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<map>

#include<cstring>

#include<string>

#include<memory.h>

using namespace std;

const long long  Inf=;

int n,i,j,k,cnt;

long long d;

map<string,int>q;

long long  m[][];

string s1,t1,x,y;

int main()

{

    while(~scanf("%d",&n)){

        if(n==-) return ;

        cnt=;

        for(i=;i<=;i++)

         for(j=;j<=;j++)

          if(i==j) m[i][j]=;

          else  m[i][j]=Inf;

        q.clear();

        cin>>s1>>t1;

        for(i=;i<=n;i++){

            cin>>x>>y>>d;

            if(q.find(x)==q.end())  q[x]=++cnt;

            if(q.find(y)==q.end())  q[y]=++cnt;

            if(m[q[x]][q[y]]>d) m[q[x]][q[y]]=d;

            if(m[q[y]][q[x]]>d) m[q[y]][q[x]]=d;

        }

        for(k=;k<=cnt;k++)

         for(i=;i<=cnt;i++)

          for(j=;j<=cnt;j++)

           if(m[i][k]+m[k][j]<m[i][j]) m[i][j]=m[i][k]+m[k][j];

        if(q[s1]>=&&q[t1]>=&&m[q[s1]][q[t1]]!=Inf) cout<<m[q[s1]][q[t1]]<<endl;

        else cout<<"-1"<<endl;

    }

    return ;

HDU2066

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<queue>

using namespace std;

queue<int>q;

const int Inf=0x3f3f3f3f;;

const int Maxm=;

const int Maxn=;

int dis[Maxn],cnt,n,Min,c,dr;

int Laxt[Maxm],Next[Maxm],To[Maxm],Len[Maxm];

int conti[Maxn],dream[Maxn];

int Win[Maxn];

void _add(int u,int v,int d){

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    Len[cnt]=d;

    Next[++cnt]=Laxt[v];

    Laxt[v]=cnt;

    To[cnt]=u;

    Len[cnt]=d;

}

void _dij()

{

    while(!q.empty()){

       int s=q.front();

       q.pop();

       Win[s]=;

       for(int i=Laxt[s];i>;i=Next[i]){

              if(dis[s]+Len[i]<dis[To[i]])

              {

                dis[To[i]]=dis[s]+Len[i];

                if(!Win[To[i]]) {

                    q.push(To[i]);

                    Win[To[i]]=;

                }

            }

       }

    }

}

int main()

{

    int m,i,j,k,x,y,z;

    while(cin>>m>>c>>dr)

    {

        memset(Laxt,,sizeof(Laxt));

        memset(Next,,sizeof(Next));

        memset(Win,,sizeof(Win));

        cnt=;

        for(i=;i<=m;i++) {

            scanf("%d%d%d",&x,&y,&z);

            _add(x,y,z);

            dis[x]=Inf;

            dis[y]=Inf;

        }

        for(i=;i<=c;i++) {

          scanf("%d",&conti[i]);

          dis[conti[i]]=;

          q.push(conti[i]);

          Win[conti[i]]=;

        }

        for(i=;i<=dr;i++) {

          scanf("%d",&dream[i]);

          dis[dream[i]]=Inf;

        }

        _dij();

        Min=Inf;

        for(j=;j<=dr;j++)

         if(Min>dis[dream[j]]) {

           Min=dis[dream[j]];

         }

        printf("%d\n",Min);

    }

    return ;

}

HDU4284

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

using namespace std;

const int inf=0x3fffffff;

int Map[][];

int City[],Ci[],Di[];

int n,m,Mon,H,T;

int used[];

bool ok;

void _tempt(int u,int k,int tmp)

{

      if(k==H)

       if(tmp>=Map[u][]){

            ok=true;

            return ;

       }

      for(int i=;i<=H;i++){

            if(used[City[i]]!=T&&Map[u][City[i]]!=inf){

                 if(tmp-Map[u][City[i]]>=Di[i])

                  {

                        used[City[i]]=T;

                        _tempt(City[i],k+,tmp-Map[u][City[i]]-Di[i]+Ci[i]);

                  }

                 if(ok) return ;

                 used[City[i]]=;

            }

      }

}

int main()

{

    int x,y,z,i,j,k;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&Mon);

        for(i=;i<=n;i++)

         for(j=;j<=n;j++)

         if(i==j) Map[i][j]=;

         else Map[i][j]=inf;

        for(i=;i<=m;i++){

           scanf("%d%d%d",&x,&y,&z);

           if(z<Map[x][y]) Map[x][y]=z;

           if(z<Map[y][x]) Map[y][x]=z;

        }

        for(k=;k<=n;k++)

         for(i=;i<=n;i++)

          for(j=;j<=n;j++)

           if(Map[i][j]>Map[i][k]+Map[k][j])

            Map[i][j]=Map[i][k]+Map[k][j];

        scanf("%d",&H);

        for(i=;i<=H;i++)

          scanf("%d%d%d",&City[i],&Ci[i],&Di[i]);

        ok=false;

        _tempt(,,Mon);

        if(ok) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}