集美大学“第15届蓝桥杯大赛(软件类)“校内选拔赛 H卯酉东海道

本文主要是介绍集美大学“第15届蓝桥杯大赛(软件类)“校内选拔赛 H卯酉东海道，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dijk + spfa思想 然后你需要存一下每个点 * l种颜色，你开个数组存一下

st[i][j] 为到达i点且到达以后是j颜色的最小距离是否已经确定了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+10;
struct Edge{ll to,col,w;bool operator<(const Edge&W)const{return w>W.w;}
};
int n,m,l,base;
bool st[N][70];
vector<Edge>g[N];
ll ans = 1e15;
ll dist[N];void spfa(int t){memset(st,0,sizeof st);priority_queue<Edge>q;q.push({1,t,0});for(int i=1;i<=n;i++)dist[i] = 1e15;dist[1] = 0;while(q.size()){auto t = q.top();q.pop();int to = t.to,col = t.col;if(st[to][col])continue;st[to][col] = true;for(auto&ts:g[to]){int tos = ts.to,cols = ts.col,ws = ts.w;if(dist[tos]>dist[to]+(cols==col?1:base)*ws){dist[tos] = dist[to] + (cols==col?1:base)*ws;q.push({tos,cols,dist[tos]});}}}ans = min(ans,dist[n]);}void solve()
{cin>>n>>m>>l>>base;for(int i=1;i<=m;i++){int a,b,c,d;cin>>a>>b>>c>>d;g[a].push_back({b,c,d});}for(int i=1;i<=l;i++)spfa(i);if(ans==1e15)cout<<-1<<"\n";else cout<<ans<<"\n";
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;_ = 1;while(_--)solve();
}

这篇关于集美大学“第15届蓝桥杯大赛(软件类)“校内选拔赛 H卯酉东海道的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---