萌新求捉虫
本地环境为WSL Ubuntu 22.04
编译参数: -g -O2 -Wall -Wextra
code:
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
inline void read(Tp &x){
x=0;
int f(1);
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
return;
}
void print(long long x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+48);
return;
}
const int n=26*2;
char u,v,anss;
int p,w,ans(0x3f3f3f3f);
#define MAXN 500005
#define INF 2147483647;
bitset<MAXN>vis;
int head[MAXN],dis[MAXN],cnt[MAXN],ecnt(0);
struct edge{
int to,next,w;
}e[MAXN];
inline int getnum(char ch){
return ch-'A';
}
inline void addedge(int u,int v,int w){
e[++ecnt]={v,head[u],w},head[u]=ecnt;
e[++ecnt]={u,head[v],w},head[v]=ecnt;
}
inline void init(){
for(int i='A';i<='z';++i){
head[i]=cnt[i]=vis[i]=0;
}
}
inline void spfa(int s){
for(int i='A';i<='z';++i)dis[i]=INF;
queue<int>q;
q.push(s),dis[s]=0,vis[s]=1;
while(!q.empty()){
int u(q.front());
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v(e[i].to);
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
read(p);
init();
for(int i=1;i<=p;++i){
scanf("%c %c",&u,&v),read(w);
addedge((int)u,(int)v,w);
}
spfa((int)'Z');
for(int i='A';i<'Z';++i){
if(ans>dis[i]){
anss=char(i);
ans=dis[i];
}
}
putchar_unlocked(anss),putchar_unlocked(' '),print(ans);
//cout<<anss<<" ";print(ans);
return 0;
}
样例本地输出:B 11
在线IDE输出:(ASCII 0) 1061109567