ylimhs

269

ylimhs
11小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N];
int dist[N];
bool st[N];
int level[N];//纪录等级
int m , n ;

/*

*/

int dijkstra(int down, int up)
{
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
dist[0] = 0 ;

for(int i = 1;  i <=n + 1 ; i ++)
{
int t = - 1;
for(int j = 0 ;  j <= n ; j ++)
if(!st[j] && (t== -1 || dist[t] > dist[j]))
t = j ;

st[t] = true;

for(int j = 1 ; j <= n ; j ++)
if(level[j] >= down &&level[j] <= up)
dist[j] = min(dist[j] , dist[t] + w[t][j]);
}
return dist[1];
}
int main()
{
cin >> m >> n ;

memset(w,0x3f,sizeof w);
for(int i = 1; i <= n ; i ++) w[i][i] = 0 ;

for(int i = 1; i <= n ; i ++)
{
int price , cnt;
cin >> price >> level[i] >> cnt;
w[0][i] = min(price,w[0][i]);
while(cnt--)
{
int id , cost;
cin >> id >> cost;
w[id][i] = min(cost,w[id][i]);
}
}
int res = 0x3f3f3f3f;
for(int i = 0; i <=level[1] ; i ++) res = min(res, dijkstra(i,i+m)) ;
cout << res ;

return 0 ;
}

ylimhs
11小时前
#include <iostream>
#include <sstream>
#include <memory.h>
#include <queue>

using namespace std;

const int N = 510;

int n, m;
int stop[N];
/*
3 7
6 7
4 7 3 6
2 1 3 5

2
*/
int g[N][N];
int dist[N];
bool st[N];

int dij()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n - 1; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}

for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}

st[t] = true;
}

return dist[n];
}

int main()
{
cin >> m >> n;
memset(g, 0x3f, sizeof g);
string line;
getline(cin, line);
while (m--) {
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt++] = p;

//每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
for (int i = 0; i < cnt; i++) {
for (int j = i + 1; j < cnt; j++) {
g[stop[i]][stop[j]] = 1;
}
}
}

int ret = dij();

if ( ret > 0x3f3f3f3f/2) cout << "NO" << endl;
else cout << ret-1 << endl;

return 0;
}

ylimhs
22小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N  = 50010;
int p[N],d[N];
int n , k ;

int find(int x){
if(p[x] != x)
{
int root = find(p[x]);
d[x]+=d[p[x]];
p[x] = root;
}
return p[x];
}

int main()
{
cin >> n >> k;

for(int i = 1; i <= n ; i ++) p[i] = i ;

int res  = 0 ;
while(k--)
{
int D ,x , y ;
cin >> D >> x >> y;

if(x > n || y > n) res ++ ;
else
{
int px = find(x),py = find(y);
if(D == 1)
{
if( px == py && (d[x] - d[y] )% 3) res ++;
else if(px != py)
{
p[px] = py;
d[px] = d[y]-d[x];
}

}else
{
if(px == py && (d[x] - d[y] -1) %3)res ++;
else
{
if(px != py)
{
p[px]=py;
d[px] = d[y]- d[x] + 1;
}
}
}
}

}
cout << res << endl;

return 0 ;

}

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2010,M=2010;;
double g[N][N];
double dist[N];
bool state[N];
int n , m ;

void dijkstra(int x)
{
//memset(dist,-0x3f,sizeof dist);
dist[x] = 1 ;
for(int i = 1; i <= n ; i ++)
{
int t = - 1;
for(int j = 1; j <= n ; j ++)
if(!state[j] && (t==-1 || dist[t] < dist[j]))
t= j ;

state[t] = true;

for(int j = 1; j <= n ; j ++)
dist[j] = max(dist[j],dist[t] * g[t][j]);
}

}

int main()
{
cin  >> n >> m ;
memset(g,-0x3f,sizeof g);
while(m--)
{
int a,b;
int c;
cin >> a>>b >> c;
g[a][b] = g[b][a] =max(g[a][b],(100.0-c) / 100);

}

int s,f;
cin >> s>>f;
dijkstra(s);
printf("%.8lf",100 / dist[f]);

return 0 ;
}

ylimhs
1天前
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 20010;
int dist[N];
bool st[N];
int n , m;
int h[N],e[N],w[N],idx,ne[N];
void add(int a, int b , int c)
{
e[idx] = b, ne[idx] = h[a],w[idx] = c , h[a] = idx ++;
}

int dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII>> heap;
memset(dist,0x3f,sizeof dist);
heap.push({0,1});

while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y,distance = t.x;
//cout << ver << endl;
if(st[ver])  continue;
st[ver] = true;

for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j],j});
}
}
}
int res = -0x3f3f3f3f;
for(int i = 1; i <= n; i ++)
{
if(dist[i]==0x3f3f3f3f) return -1;
res = max(res,dist[i]);

}
return res;

}

int main()
{

cin >> n >> m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin >> a>>b >> c;
}
cout << dijkstra() << endl;

return 0 ;
}

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2550;

int dist[N];
bool state[N];
int g[N][N];
int n,C,s,f;

int dijkstra(int start)
{
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
state[start] = false;
for(int i = 1 ; i < n ; i ++)
{
int t = - 1;
for(int j = 1; j <= n ; j ++)
if(!state[j] && (t == -1 || dist[t] > dist[j]))
t =j;
state[t] = true;
for(int j = 1; j <= n ; j ++)
dist[j] = min (dist[j] , dist[t] + g[t][j]);
}
return dist[f];
}

int main()
{
cin >> n>> C >> s >>f;

memset(g,0x3f,sizeof g);

while(C--)
{
int a, b ,c;
cin >> a >> b >>c;
g[a][b] = g[b][a] = min(g[a][b],c);
}

cout << dijkstra(s) << endl;

return 0 ;
}

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
typedef long long LL;
struct Node{
int l ,r;
}tr[N * 4];
int n,m ;
int w[N];

void pushup(int u )
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
{
u.sum = (LL)(u.sum + (u.r - u.l + 1) * add);
}

void pushdown(int u )
{
}
void build(int u , int l , int r)
{
if( l  == r)
{
tr[u] = {l,r,w[r],0};
}
else
{
tr[u] = {l,r};
int mid = l+ r>>1;
build(u << 1, l , mid), build (u << 1| 1, mid + 1, r);
pushup(u);
}
}

void modify(int u ,int l ,int r ,LL add)
{
if(tr[u].l >= l && tr[u].r <= r)
{
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid ) modify(u << 1, l , r , add);
if(r > mid)modify(u<<1 | 1, l , r, add);
pushup(u);
}
}

LL query(int u ,int l ,int r)
{
if(tr[u].l >= l  && tr[u].r <= r)
{
return tr[u].sum;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
if(l <= mid) res = (LL)(res + query(u << 1 , l , r));
if(r > mid) res = (LL)(res + query(u<<1 | 1, l , r));
return res;
}
}

int main()
{
cin >> n >> m;
for(int i = 1; i <= n ; i ++)cin>>w[i];
build(1,1,n);

while(m--)
{
char op[2];
int l ,r ,d;
scanf("%s%d%d",op,&l,&r);
if(*op == 'Q')
{

printf("%lld\n",query(1,l,r));
}
else
{
cin >> d;
modify(1,l,r,d);
}
}

return 0 ;
}

ylimhs
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;

struct Node{
int l ,r ;
}tr[N * 4];
int n ,m;
int w[N];
void pushup(int u )
{
tr[u].sum = tr[u<<1].sum + tr[u << 1 | 1].sum;
}
void eval(Node &u , LL add)
{
u.sum = (LL)(u.sum + (u.r - u.l + 1) * add);
}
void pushdown(int u)
{

}

void build(int u , int l ,int r)
{
if(l == r)
{
tr[u] = {l,r,w[r],0};
}
else
{
tr[u] = {l,r};
int mid = l + r >> 1;
build(u<<1 , l , mid ) , build(u<<1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u ,int l, int r , int add)
{
if(tr[u].l >= l && tr[u].r <= r)
{
}
else
{

pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1 , l , r, add);
if(r > mid) modify(u<<1|1, l , r, add);
pushup(u);
}
}

LL query(int u , int l)
{
if(tr[u].l == l && tr[u].r == l )
{
return tr[u].sum ;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0 ;
if(l <= mid)res +=query(u<<1 , l);
if(l > mid)res +=query(u<<1 | 1, l);

return res;
}
}

int main()
{
cin >> n >> m ;
for(int i =1 ; i <= n;  i++) cin >> w[i];

build(1,1,n);

while(m--)
{
char op[2];
int l ,r ,d;
scanf("%s%d",op,&l);
if(*op == 'Q')
{
printf("%lld\n", query(1, l));
}
else
{
cin >> r >>d ;
modify(1,l,r,d);
}
}

return 0;
}

ylimhs
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2000100;
int tr[N * 2];
int w[N];
int n ;
int lower[N],Greater[N];//記錄小和大

int lowbit(int x)
{
return x & -x;
}

void add(int x , int v)
{
for(int i = x ;i <= n ; i +=lowbit(i))
{
tr[i] +=v;
}
}

LL sum(int x)
{
LL res = 0;
for(int i = x; i  ; i -=lowbit(i))
res +=tr[i];
return res;
}

int main()
{
cin >> n ;

for(int i = 1; i <=n ; i++) cin >> w[i];

for(int i = 1; i <=  n ;i ++)
{
int y = w[i];
lower[i] = sum(y-1);
Greater[i] = sum(n)-sum(y);//总共的减去小=的数 就是大于

}

memset(tr,0,sizeof tr);

LL resv = 0 , resa = 0;

for(int i = n ; i ; i --)
{
int  y  = w[i];

resa += lower[i]*sum(y-1);
resv += Greater[i] * (sum(n) - sum(y));

}

printf("%lld %lld", resv,resa);
return 0 ;
}

ylimhs
2天前
#include <iostream>

using namespace  std;
const int N = 1e6 + 10;
int p[N];
int Size[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n , m;
cin >> n>> m ;
for(int i = 1; i <= n; i++)
{
p[i] = i;
Size[i] = 1;
}
while(m--)
{
string op;
int a, b;
cin >> op;
if(op == "C")
{
cin >>a >>b;

int pa = find(a),pb = find(b);
if(pa != pb)
{
p[pa]=pb;
Size[pb]+=Size[pa];

}

}
else if(op =="Q1")
{
cin >>a>>b;
int pa = find(a),pb = find(b);
if(pa == pb)puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << Size[find(a)]<<endl;
}
}
return 0;

}