PAT-甲级-1084-to-1087

1084 Broken Keyboard (20分)

遇到的坑：

$tolower(),toupper()$默认返回的$int$所以不能直接当成字符。

1085 Perfect Sequence (25分)

枚举每个点，然后二分取最值，一发过了。

1086 Tree Traversals Again (25分)

二叉树遍历的题目我好弱。非递归的中序遍历的栈实现，入栈序列就是先序遍历，出栈序列就是中序遍历，一直先序和中序，然后就可以递归找后序了。

1087 All Roads Lead to Rome (30分)

最短路的经典题目，输出顺序看错了，我$debug$了一个小时，呜呜呜。

就是需要多维护几个东西，输出路径就利用$pre[]$数字和栈就行了，具体看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,k,st,ed,cnt,h[N];
int num[N],sum[N],d[N],vis[N],hp[N],pre[N],pcnt[N];
struct edge{
    int to,nt,w;
}e[M];
void add(int u,int v,int w){
    e[++cnt]={v,h[u],w},h[u]=cnt;
    e[++cnt]={u,h[v],w},h[v]=cnt;
}
unordered_map<string,int>mp;
string name[N];
int id;
int fun(string a){
    if(!mp[a])  mp[a]=++id,name[id]=a;  
    return mp[a];
}
void dij(){
    mst(d,0x3f);d[st]=0,num[st]=1,sum[st]=hp[st];
    priority_queue<PII>q;
    q.push({d[st],st});
    while(!q.empty()){
        PII now=q.top();q.pop();int u=now.se;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u];i;i=e[i].nt){
            int v=e[i].to,w=e[i].w;
                if(!vis[v]&&d[v]>d[u]+w){
                    d[v]=d[u]+w;
                    sum[v]=sum[u]+hp[v];
                    num[v]=num[u],pre[v]=u;
                    pcnt[v]=pcnt[u]+1;
                    q.push({-d[v],v});
                }
                else if(d[v]==d[u]+w){
                    num[v]+=num[u];
                    if(sum[v]<sum[u]+hp[v]){
                        sum[v]=sum[u]+hp[v];
                        pre[v]=u;
                        pcnt[v]=pcnt[u]+1;
                    }
                    else if(sum[v]==sum[u]+hp[v]&&pcnt[v]>pcnt[u]+1){
                        pcnt[v]=pcnt[u]+1;
                        pre[v]=u;
                    }
                }
        }
    }stack<int>ans;
    printf("%d %d %d %d\n",num[ed],d[ed],sum[ed],sum[ed]/pcnt[ed]);
    while(ed!=st){
        ans.push(ed);
        ed=pre[ed];
    }ans.push(st);int ok=0;
    while(!ans.empty()){
        if(!ok) cout<<name[ans.top()],ok=1;
        else cout<<"->"<<name[ans.top()];ans.pop();
    }    
}
int main(){
    scanf("%d%d",&n,&k);string s;cin>>s;st=fun(s);
    for(int i=1,x;i<=n-1;i++){
        cin>>s>>x;
        int y=fun(s);hp[y]=x;
    }ed=mp["ROM"];
    for(int i=1,w;i<=k;i++){
        string u,v;cin>>u>>v>>w;
        int x=mp[u],y=mp[v];add(x,y,w);
    }dij();
    return 0;
}