PTA | L3-1 直搗黃龍 30分

思路：多關鍵字最短路，同時還要記錄最短路徑條數。

typedef struct node{int from,d,pass,kl;bool operator<(const node &x)const{if(d!=x.d) return d>x.d;if(pass!=x.pass) return pass<x.pass;return kl<x.kl;}
}node;
int n,m;
string home,en;
unordered_map<string,int> ha;
unordered_map<int,string> antHa;
int enemys[205];
int idx=0;
vector<pair<int,int>> vct[205];
int dis[205];       // 到達i城鎮的最短路
int pass[205];      // 到達i城鎮經過了多少城鎮
int kl[205];      // 到達i城鎮殺了多少人
int road[205];    // 當前城鎮從哪來
int cnt[205];     // 到達i城鎮的最短路條數
bool vis[205];
void dijkstra(int s){for(int i=0;i<=idx;i++) dis[i]=LONG_LONG_MAX/2;dis[s]=0,pass[s]=0,kl[s]=0,cnt[s]=1;priority_queue<node> pq;pq.emplace(node{s,0,0,0});while(!pq.empty()){int from=pq.top().from;pq.pop();if(vis[from]) continue;vis[from]=true;for(auto v:vct[from]){int to=v.first,w=v.second;if(dis[to]>dis[from]+w){    // 距離更短dis[to]=dis[from]+w;pass[to]=pass[from]+1;kl[to]=kl[from]+enemys[to];road[to]=from;cnt[to]=cnt[from];pq.emplace(node{to,dis[to],pass[to],kl[to]});}else if(dis[to]==dis[from]+w){cnt[to]+=cnt[from];if(pass[to]<pass[from]+1){pass[to]=pass[from]+1;kl[to]=kl[from]+enemys[to];road[to]=from;pq.emplace(node{to,dis[to],pass[to],kl[to]});}else if(pass[to]==pass[from]+1){if(kl[to]<kl[from]+enemys[to]){kl[to]=kl[from]+enemys[to];road[to]=from;pq.emplace(node{to,dis[to],pass[to],kl[to]});}}}}}
}
void solve(){          // 過了樣例就交，一發入魂！~，手術刀一樣精準，挺典型的最短路題目，逐次遞減的優先級。cin>>n>>m;cin>>home>>en;ha[home]=++idx;antHa[idx]=home;for(int i=1;i<=n-1;i++){string town; cin>>town;if(ha[town]==0) ha[town]=++idx,antHa[idx]=town;int x; cin>>x;enemys[ha[town]]=x;}for(int i=1;i<=m;i++){string t1,t2; cin>>t1>>t2;int d; cin>>d;vct[ha[t1]].e(ha[t2],d);vct[ha[t2]].e(ha[t1],d);}dijkstra(ha[home]);int cur=ha[en];stack<string> stk;while(cur!=1){stk.emplace(antHa[cur]);cur=road[cur];}cout<<home;while(!stk.empty()){cout<<"->"<<stk.top();stk.pop();}cout<<endl;cout<<cnt[ha[en]]<<" "<<dis[ha[en]]<<" "<<kl[ha[en]];
}

PTA | L3-2 拼題A打卡獎勵? 30分


?

思路：背包問題，但是要優化：

curSum+=minute[i]; ? ? ? ?// 不必每次都從m開始轉移,這樣很白白跑很多不必要的循環..學到了
curSum=min(curSum,m); ? ? // 細節!@!

void solve(){
//    cout<<365*24*60*1000;    // 5e8int n,m; cin>>n>>m;int minute[1003]={0};int coin[1003]={0};for(int i=1;i<=n;i++) cin>>minute[i];for(int i=1;i<=n;i++) cin>>coin[i];vector<int> dp(m+5,0);int ans=0,curSum=0;for(int i=1;i<=n;i++){curSum+=minute[i];        // 不必每次都從m開始轉移,這樣很白白跑很多不必要的循環..學到了curSum=min(curSum,m);     // 細節!@!for(int j=curSum;j>=minute[i];j--){dp[j]=max(dp[j],dp[j-minute[i]]+coin[i]);ans=max(ans,dp[j]);}}cout<<ans;
}