hdu 2112 最短路

时间：2021-07-10 14:56:07

本来是拿来复习一下map的，没想搞了半天，一直wa，最后发现预处理没有处理到所有的点

就是个最短路

Sample Input

6

xiasha westlake

xiasha station 60

xiasha ShoppingCenterofHangZhou 30

station westlake 20

ShoppingCenterofHangZhou supermarket 10

xiasha supermarket 50

supermarket westlake 10

-1

Sample Output
50

Hint:

The best route is:

xiasha->ShoppingCenterofHangZhou->supermarket->westlake

虽然偶尔会迷路，但是因为有了你的帮助

**和**从此还是过上了幸福的生活。

――全剧终――
 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 const int maxint=;

 //printf("----\n");

 using namespace std;

 int m,t;

 int tot=;

 map<string,int> st;

 int c[][],dist[];

 void dijkstra(int u,int n)

 {

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

     bool vis[];

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

     {

         vis[i]=;

         dist[i]=c[u][i];

     }

     vis[u]=;

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

     {

         int temp=maxint;

         int k=u;

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

         {

             if(!vis[j]&&dist[j]<temp)

             {

                 temp=dist[j];

                 k=j;

             }

         }

         if(temp==maxint)    break;

         vis[k]=;

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

         {

             if(!vis[j]&&c[k][j]<maxint)

             {

                 if(dist[k]+c[k][j]<dist[j])

                     dist[j]=dist[k]+c[k][j];

             }

         }

     }

 }

 int main()

 {

     int i,j,k,n;

     //freopen("1.in","r",stdin);

     while(scanf("%d",&n)!=EOF)

     {

         bool flag=;

         if(n==-)   break;

         st.clear();

         char s[],e[];

         scanf("%s%s",s,e);

         if(strcmp(s,e)==)

         {

             flag=;

         }

         st[s]=;

         st[e]=;

         tot=;

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

         {

             for(j=;j<=;j++)   c[i][j]=c[j][i]=((i==j)?:maxint);

         }

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

         {

             dist[i]=maxint;

         }

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

         {

             int w;

             scanf("%s%s%d",s,e,&w);

             if(!st[s]) st[s]=tot++;

             if(!st[e]) st[e]=tot++;

             c[st[s]][st[e]]=c[st[e]][st[s]]=w;

         }

         dijkstra(,tot);

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

         else if(dist[]==maxint) printf("-1\n");

         else

             printf("%d\n",dist[]);

     }

     return ;

 }

2015-04-24：这个是kuangbin模板的，检测了一下，算法里的起点是从0开始的，那个优化代码不知道怎么就wa了，等刷到kuang大神的最短路再看吧

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 #define typec int

 const typec INF=;//防止后面溢出，这个不能太大

 int c[MAXN][MAXN],tot=,dist[];

 bool vis[MAXN];

 int pre[MAXN];

 void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg)

 {

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

     {

         lowcost[i]=INF;vis[i]=false;pre[i]=-;

     }

     lowcost[beg]=;

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

     {

         int k=-;

         int Min=INF;

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

             if(!vis[i]&&lowcost[i]<Min)

             {

                 Min=lowcost[i];

                 k=i;

             }

         if(k==-)break;

         vis[k]=true;

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

         if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])

         {

             lowcost[i]=lowcost[k]+cost[k][i];

             pre[i]=k;

         }

     }

 }

 map<string,int> st;

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(scanf("%d",&n)!=EOF)

     {

         bool flag=;

         if(n==-)   break;

         st.clear();

         char s[],e[];

         scanf("%s%s",s,e);

         if(strcmp(s,e)==)

         {

             flag=;

         }

         st[s]=;

         st[e]=;

         tot=;

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

         {

             for(j=;j<=;j++)   c[i][j]=c[j][i]=((i==j)?:INF);

         }

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

         {

             dist[i]=INF;

         }

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

         {

             int w;

             scanf("%s%s%d",s,e,&w);

             if(!st[s]) st[s]=tot++;

             if(!st[e]) st[e]=tot++;

             c[st[s]][st[e]]=c[st[e]][st[s]]=w;

         }

         Dijkstra(c,dist,tot,);

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

         else if(dist[]==INF) printf("-1\n");

         else

             printf("%d\n",dist[]);

     }

 }

相关文章