B1072 Gas Station (最短路)

B1072 Gas Station (30分)

//对每一个加油站跑一次最短路，跑完后，遍历一遍dis数组，求出所需要的
这题卡在这个点卡了半天！！！
数组开1e3+20，开到1e+10就gg了( * ^ _ ^ * )

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=1e3+20;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
int n,m,k,d;
int G[MAX][MAX];
int dis[MAX];
int book[MAX];
int change(string str)
{
    int sum=0;
    if(str[0]=='G')
    {
        for(int i=1;i<str.size();i++)
        {
            sum=sum*10+(str[i]-'0');
        }
        return sum+n;
    }
    else
    {
        for(int i=0;i<str.size();i++)
        {
            sum=sum*10+(str[i]-'0');
        }
        return sum;
    }
}
void dijkstra(int x)
{
    memset(book,0,sizeof(book));
    fill(dis,dis+MAX,INF);
    dis[x]=0;
    for(int i=1;i<=n+m;i++)
    {
        int MIN=INF,u=-1;
        for(int j=1;j<=n+m;j++)
        {
            if(dis[j]<MIN&&book[j]==0)
            {
                MIN=dis[j];
                u=j;
            }
        }
        if(u==-1)
            return ;
        book[u]=1;
        for(int v=1;v<=n+m;v++)
        {
            if(book[v]==0&&G[u][v]!=INF&&dis[v]>dis[u]+G[u][v])
            {
                    dis[v]=dis[u]+G[u][v];
            }
        }
    }
}
int main()
{
   scanf("%d%d%d%d",&n,&m,&k,&d);
   fill(G[0],G[0]+MAX*MAX,INF);
   for(int i=0;i<k;i++)
   {
       string a,b;
       int dis;
       int x,y;
       cin>>a>>b;
       x=change(a);
       y=change(b);
       scanf("%d",&dis);
       G[x][y]=G[y][x]=dis;
   }
   int id=-1;
   double maxdis=0;
   double minavg=INF;
   for(int i=n+1;i<=n+m;i++)
   {
       dijkstra(i);
       int flag=0;
       double mind=INF;
       double davg=0;
       for(int j=1;j<=n;j++)
       {
           if(dis[j]>d)
           {
               flag=1;
               break;
           }
           if(mind>dis[j])
           {
               mind=dis[j];
           }
           davg+=(dis[j]*1.0);
       }
       if(flag==1)
        continue;
       if(maxdis<mind)
       {
           maxdis=mind;
           minavg=davg;
           id=i;
       }
       else if(maxdis==mind&&minavg>davg)
       {
           id=i;
           minavg=davg;
       }
   }
   if(id==-1)
        cout<<"No Solution"<<endl;
   else
   {
       printf("G%d\n", id - n);
       printf("%.1f %.1f\n",maxdis,minavg/n);
   }
    return 0;
}