icpc南昌网络赛
B. Fire-Fighting Hero
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1004;
const int V = 1e6 + 3;
ll ver[V*5],tot,Next[V*5],head[maxn],vis[maxn],u[maxn],v[maxn][maxn];
ll edge[V*5],dis[maxn],d[maxn];
priority_queue<pair<ll,ll> > qq;
priority_queue<pair<ll,ll> > PQ;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void add(ll x,ll y,ll z)
{
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void Dij(ll s)
{
//cout<<qq.size();
memset(vis,0,sizeof(vis));
for(ll i=0;i<maxn;i++) d[i]=9e17;
d[s]=0;
//cout<<qq.size();
while(!qq.empty()) qq.pop();
qq.push(make_pair((ll)0,s));
//cout<<"asd";
while(!qq.empty())
{
ll z;
ll x=qq.top().second,y; qq.pop();
if(vis[x]) continue;
vis[x]=1;
for(ll i=head[x];i;i=Next[i]) {
y=ver[i],z=edge[i];
if(!vis[y]&&d[y]>d[x]+z) {
d[y]=d[x]+z;
qq.push(make_pair(-d[y],y));
}
}
}
}
void dij(ll s)
{
memset(vis,0,sizeof(vis));
for(ll i=0;i<maxn;i++) dis[i]=9e17;
dis[s]=0;
while(!PQ.empty()) PQ.pop();
PQ.push(make_pair((ll)0,s));
while(!PQ.empty())
{
ll z;
ll x=PQ.top().second,y; PQ.pop();
if(vis[x]) continue;
vis[x]=1;
for(ll i=head[x];i;i=Next[i]) {
y=ver[i],z=edge[i];
if(!vis[y]&&dis[y]>dis[x]+z) {
dis[y]=dis[x]+z;
PQ.push(make_pair(-dis[y],y));
}
}
}
}
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n,m,s,k,x,y; ll c,z;
memset(v,0,sizeof(v));
memset(head,0,sizeof(head));
tot=0;
scanf("%lld%lld%lld%lld%lld",&n,&m,&s,&k,&c);
for(ll i=1;i<=k;i++) {
scanf("%lld",&u[i]);
add(n+1,u[i],(ll)0); //add(u[i],n+1,(ll)0);
}
for(ll i=1;i<=m;i++) {
scanf("%lld%lld%lld",&x,&y,&z);
if(!v[x][y]) {
v[x][y] = z;
v[y][x] = z;
}
else {
v[x][y] = min(v[x][y],z);
v[y][x] = v[x][y];
}
}
for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++)
{
if(v[i][j])add(i,j,v[i][j]);
}
//cout<<qq.size()<<"\n";
Dij(s);
dij(n+1);
ll a=0,b=0;
for(ll i=1;i<=n;i++) a=max(a,d[i]);
for(ll i=1;i<=n;i++) b=max(b,dis[i]);
if(a<=b*c) printf("%lld\n",a);
else printf("%lld\n",b);
}
return 0;
}
/*
4
4 7 3 2 2
1 4
1 2 7
1 3 2
1 4 6
2 1 1
2 4 1
3 2 1
3 4 3
4 7 3 2 2
1 4
1 2 7
1 3 2
1 4 6
2 1 1
2 4 1
3 2 1
3 4 3
4 7 3 2 2
1 4
1 2 7
1 3 2
1 4 6
2 1 1
2 4 1
3 2 1
3 4 3
4 7 3 2 2
1 4
1 2 7
1 3 2
1 4 6
2 1 1
2 4 1
3 2 1
3 4 3
*/ C: code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 3;
char s[maxn];
struct T {
int dp[5][5],l,r;
}t[maxn<<2];
T add(T a,T b,int l,int r)
{
T c;
c.l=l,c.r=r;
for(int i=0;i<5;i++) for(int j=0;j<5;j++)
{
c.dp[i][j]=INF;
for(int k=0;k<5;k++) c.dp[i][j]=min(c.dp[i][j],a.dp[i][k]+b.dp[k][j]);
}
return c;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r) {
for(int i=0;i<5;i++) for(int j=0;j<5;j++) t[p].dp[i][j]=(i==j?0:INF);
if(s[l]=='2') t[p].dp[0][1]=0,t[p].dp[0][0]=1;
else if(s[l]=='0') t[p].dp[1][2]=0,t[p].dp[1][1]=1;
else if(s[l]=='1') t[p].dp[2][3]=0,t[p].dp[2][2]=1;
else if(s[l]=='9') t[p].dp[3][4]=0,t[p].dp[3][3]=1;
else if(s[l]=='8') t[p].dp[4][4]=t[p].dp[3][3]=1;
return;
}
int mid=(l+r)>>1;
build(p*2,l,mid); build(p*2+1,mid+1,r);
t[p]=add(t[p*2],t[p*2+1],t[p].l,t[p].r);
}
T query(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r) return t[p];
int mid=(t[p].l+t[p].r)>>1;
if(mid<l) return query(p*2+1,l,r);
else if(mid>=r) return query(p*2,l,r);
else return add(query(p*2,l,r),query(p*2+1,l,r),t[p].l,t[p].r);
}
int main()
{
int n,q;
scanf("%d%d%s",&n,&q,s+1);
reverse(s+1,s+n+1);
build(1,1,n);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
T ans=query(1,n-r+1,n-l+1);
printf("%d\n",ans.dp[0][4]==INF?-1:ans.dp[0][4]);
}
return 0;
} #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n==1) cout<<18000<<"\n";
else cout<<0<<"\n";
}
return 0;
} code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sd(a) scanf("%d",&a)
#define sld(a) scanf("%lld",&a)
#define pr(a) printf("%d\n",a)
#define per(a,b,c) for(int a=b;a<c;++a)
#define perr(a,b,c) for(int a=b;a<=c;++a)
#define rua() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sl(a) scanf("%[^\n]",&a);getchar();
#define ss(a) scanf("%s",a)
const int inf=0x3f3f3f3f;
const int mod=998244353;
map<ll,ll>as;
int v[20001];
struct matrix{
ll a[3][3];
matrix(){
memset(a,0,sizeof(a));
}
};
map<ll,matrix> mp;
matrix ans;
matrix to;
ll MOD(ll x, ll y){
return x - y * (x / y);
}
inline matrix mul_matrix(matrix ans,matrix to){
matrix temp;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
for(int k=0;k<3;++k)
{
temp.a[i][j]=MOD((temp.a[i][j]+MOD(ans.a[i][k]*to.a[k][j],mod)),mod);
}
return temp;
}
ll re=1;
inline matrix pow_m(matrix to,ll n)
{
matrix temp=ans;//单位矩阵
temp.a[0][0]=1;
temp.a[1][1]=1;
temp.a[2][2]=1;
re=1;
while(n)
{
++re;
if(n&1){temp=mul_matrix(temp,to);}
// if(v[re])
// to=mp[re];
// else
{
to=mul_matrix(to,to);
//mp[re]=to;
//v[re]=1;
}
n>>=1;
}
return temp;
}
int main()
{
ll q,n;
to.a[0][1]=1;to.a[1][2]=1;
to.a[2][1]=2;to.a[2][2]=3;
ans.a[0][0]=0;ans.a[1][0]=1;ans.a[2][0]=3;
mp[1]=to;
sld(q);
sld(n);
ll myans=0;
ll temp=0;
matrix mat=pow_m(to,n);
matrix ansss=mul_matrix(mat,ans);
temp=ansss.a[0][0];
myans^=temp;
mp[n]=mat;
per(i,1,q)
{
n=temp*temp^n;
if(as.count(n))//有
{
temp=as[n];
}
else
{
mat=pow_m(to,n);
ansss=mul_matrix(mat,ans);temp=ansss.a[0][0];
as[n]=ansss.a[0][0];
//mp[n]=mat;
}
myans^=temp;
}
cout<<myans%mod<<endl;
} 
