560

1eave
R-O-Y

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

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

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

for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);

cout << f[n][m] << endl;

return 0;
}


#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];//前缀和
int f[N][N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

for(int len=2;len<=n;len++)
for (int i = 1; i + len - 1 <= n; i++)
{
int j = len - 1 + i;
f[i][j] = 1e8;
for (int k = i; k < j; k++)
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}

cout << f[1][n] << endl;

return 0;
}


### 朴素写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];

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

for(int i=1;i<=n;i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}

cout << f[n][m] << endl;
return 0;
}


### 优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N];

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

for(int i=1;i<=n;i++)
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;
return 0;
}


### 朴素写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];

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

for(int i=1;i<=n;i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}

cout << f[n][m] << endl;

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=210,INF=1e9;

int n,m,Q;
int d[N][N];

void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
cin>>n>>m>>Q;

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) d[i][j]=0;
else d[i][j]=INF;

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

d[a][b]=min(d[a][b],w);
}

floyd();

while(Q--)
{
int a,b;
scanf("%d%d",&a,&b);

if(d[a][b]>INF/2) cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=100010;

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

void add(int x,int y,int c)
{
w[idx]=c;
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}

bool spfa()
{

queue<int>q;

for(int i=1;i<=n;i++)
{
st[i]=true;
q.push({i});
}

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

st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n) return true;
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return false;
}

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

memset(h,-1,sizeof h);

for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}

if(spfa()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=100010;

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

void add(int x,int y,int c)
{
w[idx]=c;
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}

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

queue<int>q;
q.push(1);

st[1]=true;

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

st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return dist[n];
}

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

memset(h,-1,sizeof h);

for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}

int t=spfa();

if(t==0x3f3f3f3f) cout<<"impossible"<<endl;
else cout<<t<<endl;

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=510,M=10010;

int n,m,k;
int d[N],backup[N];

struct Edge
{
int a,b,w;
}edges[M];

int bellman_ford()
{
memset(d,0x3f,sizeof d);
d[1]=0;

for(int i=0;i<k;i++)
{
memcpy(backup,d,sizeof d);
for(int j=0;j<m;j++)
{
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
d[b]=min(d[b],backup[a]+w);
}
}
return d[n];
}

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

for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}

bellman_ford();

if(d[n] > 0x3f3f3f3f / 2) cout<<"impossible"<<endl;
else cout<<d[n]<<endl;

return 0;
}


//堆优化版的Dijkstra算法   针对针对单源最短路中边权都为正的稀疏图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 150010;

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

int n, m;

void add(int x, int y, int c)
{
w[idx] = c;
e[idx] = y;
ne[idx] = h[x];
h[x]=idx++;
}

int dijkstra()
{
memset(d, 0x3f, sizeof d);
d[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;    //小根堆

heap.push({ 0,1 }); //first必须为距离
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 (d[j] > distance + w[i])
{
d[j] = distance + w[i];
heap.push({ d[j],j });
}
}
}

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

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

while (m--)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
add(x, y, c);
}

cout << dijkstra() << endl;

return 0;
}


//堆优化版的Dijkstra算法   针对针对单源最短路中边权都为正的稀疏图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 150010;

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

int n, m;

void add(int x, int y, int c)
{
w[idx] = c;
e[idx] = y;
ne[idx] = h[x];
h[x]=idx++;
}

int dijkstra()
{
memset(d, 0x3f, sizeof d);
d[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;    //小根堆

heap.push({ 0,1 }); //first必须为距离
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 (d[j] > distance + w[i])
{
d[j] = distance + w[i];
heap.push({ d[j],j });
}
}
}

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

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

while (m--)
{
int x, y, c;
scanf_s("%d%d%d", &x, &y, &c);
add(x, y, c);
}

cout << dijkstra() << endl;

return 0;
}