ccf csp 202212星际网络 4分（未优化）-Toy模板网

这篇具有很好参考价值的文章主要介绍了ccf csp 202212星际网络 4分（未优化）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

思路：1. 将卫星看作边的一部分，经过卫星的延迟即为该边的权重。2. 因为还要求返回的时间，所以是求任意两点的最短路径，用Floyd算法。3. 用快速幂处理爆long long文章来源地址https://www.toymoban.com/news/detail-631855.html

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = -1;
const ll mod = 1e9+7;

// 计算T爆ll，用快速幂处理
long long cheng(long long a,long long b)
{
	long long s = 0;
	while (b) 
	{
		if (b&1) s=(s+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return s;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    // freopen("../io/input.txt", "r", stdin);
    int n,m;
    cin>>n>>m;
    int l1,r1,l2,r2,a,b,len=n+1;
    ll Edge[len][len];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            Edge[i][j] = INF;
        }
        Edge[i][i] = 0;
    }
    // 将卫星看作有向边的一部分，T即为边的代价
    for(int i=1; i<=m; i++){
        cin>>l1>>r1>>l2>>r2>>a>>b;
        ll T = cheng(a,pow(2, b));
        for(int j=l1; j<=r1; j++){
            for(int k=l2; k<=r2; k++){
                if (j==k) continue;
                Edge[j][k] = T;
            }
        }
    }
    // Floyd
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(Edge[i][k]==INF||Edge[k][j]==INF){
                    continue;
                }
                ll x = (Edge[i][k]+Edge[k][j]);
                if(Edge[i][j]==INF|| x<Edge[i][j]){
                    Edge[i][j] = x;
                }
            }
        }
    }

    for(int i=2; i<=n; i++){
        if (Edge[1][i]==INF||Edge[i][1]==INF){
            cout<<INF<<" ";
            continue;
        }
        cout<<(Edge[1][i]+Edge[i][1])%mod<<" ";
    }
    return 0;
}