E.lena

15.2万

E0柒
hoool
Ascension
find_lose
-YyyyL
h-h

L1_
H小轩

Themove

15163669008
har
KTpro

E.lena
17小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N=100010,M=300010;

int n,m,k,q;

int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
memset(dist, 0x3f, sizeof dist);
dist[0] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 0});

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second, distance = t.first;

if (st[ver]) continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}

int main()
{
cin>>n>>m;
memset(h, -1, sizeof h);
while (m -- )
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}

cin>>k;

for(int i=1;i<=k;i++)//建立超级源点,连接每个商店,且权值为0,即可达到每个商店都可以是起点的目的
{
int x;
scanf("%d",&x);
}

cin>>q;

dijkstra();

for(int i=1;i<=q;i++)
{
int start;
cin>>start;
printf("%d\n",dist[start]);
}
}


E.lena
17小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

const int N = 25010,M=160010;

typedef pair<int, int> PII;

int n,P,R,S;
int dist[N],din[N],id[N];//id[i]表示i的所属集合的编号,din[i]表示id为i的点的集合的入度;
vector<int> block[N];//block[i]存储的是id为i的点的集合
int idcnt;//id的编号分配
queue<int> q;//入度为0的集合编号入队
bool st[N];//最短路判重
int h[N], e[M], w[M], ne[M], idx;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u,int idn)
{
id[u]=idn;
block[idn].push_back(u);

for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!id[j]) dfs(j,idn);
}
}

void dijkstra(int tid)
{
priority_queue<PII,vector<PII>,greater<PII>> heap;

for(int i=0;i<block[tid].size();i++)
heap.push({dist[block[tid][i]],block[tid][i]});

while(heap.size())
{
auto t=heap.top();
heap.pop();

int u=t.y;
if(st[u]) continue;
st[u]=true;

for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(id[j]!=id[u]&&--din[id[j]]==0) q.push(id[j]);

if(dist[j]>dist[u]+w[i])
{
dist[j]=dist[u]+w[i];
if(id[j]==id[u]) heap.push({dist[j],j});
}
}
}
}

void topsort()
{
memset(dist,0x3f,sizeof dist);
dist[S]=0;

for(int i=1;i<=idcnt;i++)
if(!din[i]) q.push(i);

while(q.size())
{
auto t=q.front();
q.pop();

dijkstra(t);
}
}

int main()
{
memset(h, -1, sizeof h);
cin>>n>>R>>P>>S;

for(int i=1;i<=R;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}

for(int i=1;i<=n;i++)
if(!id[i]) dfs(i,++idcnt);//划分集合的过程

while(P--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
din[id[b]]++;//b所属的集合入度+1
}

topsort();//拓步排序求dijkstra

for(int i=1;i<=n;i++)
if(dist[i]>0x3f3f3f3f/2) printf("NO PATH\n");
else printf("%d\n",dist[i]);

return 0;
}


E.lena
17小时前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1000010;

int n;
char str[N];
int ne[N];

int main()
{
int T=1;
while(cin>>n,n)
{
scanf("%s",str+1);
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && str[i] != str[j + 1]) j = ne[j];
if (str[i] == str[j + 1]) j ++ ;
ne[i] = j;
}

printf("Test case #%d\n", T ++ );

for(int i=1;i<=n;i++)
{
int t = i - ne[i];
if (i % t == 0 && i / t > 1)
printf("%d %d\n", i, i / t);
}
puts("");
}

return 0;
}


E.lena
1天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;

int g[N][N],level[N];
int dist[N];
bool st[N];
int n,m;

int dijkstra(int minx,int maxi)
{
memset(dist,0x3f,sizeof dist);
memset(st,false,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]>=minx&&level[j]<=maxi)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}

return dist[1];
}

int main()
{
cin>>m>>n;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++)
{
int p,l,x;
g[i][i]=0;
scanf("%d%d%d",&p,&l,&x);
level[i]=l;
g[0][i]=p;
while(x--)
{
int a,b;
scanf("%d%d",&a,&b);
g[a][i]=min(g[a][i],b);
}
}

int res=0x3f3f3f3f;
for(int i=level[1]-m;i<=level[1]+m;i++) res=min(res,dijkstra(i,i+m));

printf("%d",res);

return 0;
}


E.lena
2天前
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=150010;

int h[N],e[N],ne[N],w[N],idx,dist[N];
int n,m;
bool st[N];

void insert(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

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

while(heap.size())
{
auto t=heap.top();
heap.pop();

int u=t.second;
if(st[u]) continue;
st[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(dist[u]+w[i]<dist[j])
{
heap.push({dist[u]+w[i],j});
dist[j]=dist[u]+w[i];
}
}
}

if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);

while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c);
}

printf("%d",dijkstra());
}


E.lena
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=510;

int g[N][N];
int dist[N];
bool st[N];
int n,m;

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

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

st[t]=true;

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

if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}

int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
}

printf("%d",dijkstra());

return 0;
}


E.lena
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110,M=10010;

int n;
int q[N],d[N];
int h[N],e[M],ne[M],idx;

void insert(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
int tt=-1,hh=0;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;

while(hh<=tt)
{
auto t=q[hh++];

for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
d[j]--;
if(!d[j]) q[++tt]=j;
}
}
}

int main()
{
cin>>n;
memset(h,-1,sizeof h);

for(int i=1;i<=n;i++)
{
int k;
while(cin>>k,k)
{
if(k==0) break;
insert(i,k);
d[k]++;
}
}

topsort();

for(int i=0;i<n;i++) printf("%d ",q[i]);

return 0;
}


E.lena
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=100010;

int d[N],q[N];
int h[N],e[N],ne[N],idx;
int n,m;

void insert(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool topsort()
{
int tt=-1,hh=0;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;

while(hh<=tt)
{
auto t=q[hh++];

for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
d[j]--;
if(!d[j]) q[++tt]=j;
}
}

if(tt==n-1) return true;
return false;
}

int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;

while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
insert(a,b);
d[b]++;
}

if(topsort()) for(int i=0;i<n;i++) printf("%d ",q[i]);
else printf("-1");

return 0;
}


E.lena
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 10;

int n, m, k;
int g[N][N];
unordered_set<int> S;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int u, int num)
{
if (u == k) S.insert(num);
else
{
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m)
dfs(a, b, u + 1, num * 10 + g[a][b]);
}
}
}

int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
scanf("%d", &g[i][j]);

for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
dfs(i, j, 0, g[i][j]);

printf("%d\n", S.size());
return 0;
}


E.lena
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=20;

int n,ans;
bool st[N],backup[N];

bool check(int a,int c)
{
long long b=(long long)n*c-(long long)a*c;

if(!a||!b||!c) return false;

memcpy(backup,st,sizeof st);

while(b)
{
int x=b%10;
if(!x) return false;
if(backup[x]) return false;
backup[x]=true;
b/=10;
}

for(int i=1;i<=9;i++)
if(!backup[i]) return false;

return true;
}

void dfs_c(int u,int a,int c)
{
if(u>9) return ;

if(check(a,c)) ans++;

for(int i=1;i<=9;i++)
if(!st[i])
{
st[i]=true;
dfs_c(u+1,a,c*10+i);
st[i]=false;
}
}

void dfs_a(int u,int a)
{
if(a>=n) return ;

dfs_c(u,a,0);

for(int i=1;i<=9;i++)
if(!st[i])
{
st[i]=true;
dfs_a(u+1,a*10+i);
st[i]=false;
}
}

int main()
{
cin>>n;

dfs_a(1,0);

printf("%d",ans);
}