很裸的最短路问题,就是输入格式比较怪异,不过也还好。。。。
code:
/* ID:yueqi LANG:C++ TASK:comehome */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits.h> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("comehome.in","r",stdin) #define writef freopen("comehome.out","w",stdout) const int maxn = 53; const long long BigP=999983; const long long INF = 0x5fffffff; const int dx[]={-1,0,1,0}; const int dy[]={0,1,0,-1}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; int N,dis[maxn],edge[maxn][maxn]; bool vis[maxn]; int getNo(char c){ if ((c>='a')&&(c<='z')) return (c-'a'+27); if ((c>='A')&&(c<='Z')) return (c-'A'+1); } void spfa(int s){ int tmp; queue<int> q; vis[s]=true; dis[s]=0; q.push(s); while(!q.empty()){ tmp=q.front();q.pop(); vis[tmp]=false; FOR(i,1,52){ if(edge[tmp][i]==INF) continue; if(dis[i]>dis[tmp]+edge[tmp][i]){ dis[i]=dis[tmp]+edge[tmp][i]; if(!vis[i]){ vis[i]=true; q.push(i); } } } } // FOR(i,1,26) printf("dis[%d]=%d\n",i,dis[i]); int minn=INF,k; FOR(i,1,25){ if(dis[i]<minn){ minn=dis[i]; k=i; } } printf("%c %d\n",(char)(k+'A'-1),minn); } int main(){ readf; writef; FF(i,maxn) FF(j,maxn){ dis[i]=INF; edge[i][j]=INF; } SD(N); int w,p,q; char ch1,ch2; FOR(i,1,N){ getchar(); scanf("%c %c %d",&ch1,&ch2,&w); p=getNo(ch1);q=getNo(ch2); edge[p][q]=edge[q][p]=min(edge[p][q],w); } //puts("!!"); spfa(26); return 0; }