89分,第七个点挂了(SPFA)

P1529 [USACO2.4] 回家 Bessie Come Home

AC了,此帖忽略 附上AC code: ```cpp #include <bits/stdc++.h> using namespace std; int P,minn=1e9+7; int mp[105][105]; char x,y,minc; int w; int chan(char a) { if(a<='z' && a>='a') { return int(a-'a'+1); } else if(a<='Z' && a>='A'){ return int(a-'A'+27); } } int dis[1005]; bool in[1005]; queue<int> q; void spfa(int st) { dis[st]=0;in[st]=true; q.push(st); while(!q.empty()) { int x=q.front();q.pop(); in[x]=false; for(int i=1;i<=52;i++) { if(mp[x][i]!=0){ if(dis[i]>dis[x]+mp[x][i]) { dis[i]=dis[x]+mp[x][i]; if(!in[i]) { q.push(i); in[i]=true; } } } } } } int main() { scanf("%d",&P); for(int i=1;i<=P;i++) { cin>>x>>y>>w; if(mp[chan(x)][chan(y)]) mp[chan(x)][chan(y)]=min(mp[chan(x)][chan(y)],w); if(mp[chan(y)][chan(x)]) mp[chan(y)][chan(x)]=min(mp[chan(y)][chan(x)],w); if(!mp[chan(x)][chan(y)])mp[chan(x)][chan(y)]=w; if(!mp[chan(y)][chan(x)])mp[chan(y)][chan(x)]=w; } memset(dis,0x7f,sizeof(dis)); spfa(52); for(int i=27;i<52;i++) { if(dis[i]<minn) { minn=dis[i]; minc=char(i-27+'A'); } } printf("%c %d\n",minc,minn); return 0; } ```
by tuzhewen @ 2019-11-09 22:58:20


@[tuzhewen](/user/117648) 精 Dij 震 怒 (滑稽
by Belarus @ 2019-11-09 22:59:18


|