最短路径 | 1072 全源最短路径+细节

这题是个细节题。因为读漏了一个条件，导致我一直wa，思考人生。编码的时候状态也不好，是在图书馆编码的，没有用vs这种调试神器差错，导致“变量写错”这样的bug查了很久。

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>


#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 2000
#define MAX (1<<30)-1
#define V vector<int>

using namespace std;

int g[LEN][LEN];
int vis[LEN];
int dist[LEN];

int n,m,ds,k;

int proc(string s){
    int delta=0,re;
    if(s[0]=='G'){
        delta=n;
        s=s.substr(1,s.size()-1);
    }
    sscanf(s.c_str(),"%d",&re);
    re+=delta;
    return re;
}

void dij(int s){
    fill(dist,dist+LEN,MAX);
    memset(vis,0,sizeof vis);
    dist[s]=0;
    int i;
    while(1){
        int u=-1,d=MAX;
        F(i,1,n+m+1) if(!vis[i] && dist[i]<d){
            d=dist[i];
            u=i;
        }
        if(u<0) return;
        vis[u]=1;
        F(i,1,n+m+1) if(!vis[i] && dist[u]+g[u][i]<dist[i]){
            dist[i]=dist[u]+g[u][i];
        }
    }
}

int main(){
//    freopen("1072_1.txt","r",stdin);
    int i,j,a,b,c;
    I("%d%d%d%d",&n,&m,&k,&ds);
    fill(g[0],g[0]+LEN*LEN,MAX);
    FF(i,k){
        char buf[LEN];
        I("%s",buf);
        a=proc(buf);        
        I("%s",buf);
        b=proc(buf);
        I("%d",&c);
        g[a][b]=c;
        g[b][a]=c;
    }
    int ans=-1;
    int ans_max=-1;
    int ans_sum;
    F(i,n+1,n+m+1){
        dij(i);
        int min_d=MAX;
        bool isOK=1;
        int sum=0;
        F(j,1,n+1){
            sum+=dist[j];
            if(dist[j]>ds){
                isOK=0;
                goto END;
            }
            if(dist[j]<min_d){
                min_d=dist[j];
            }
        }
        if(min_d>ans_max || (min_d==ans_max && sum<ans_sum)){
            ans=i;
            ans_max=min_d;
            ans_sum=sum;
        }
        END:;
    }
    ans-=n;
    if(ans<0){
        OL("No Solution");
    }else{
        O("G%d
%.1f %.1f",ans,(double)ans_max,ans_sum/(double)n);
        
    }
    return 0;
}