2768

LIKL
chase_6
tzssdfdj@sdfdj.com余@sdfdj.com
lovely_haimo

GZNU第一深情
Mark1St

incra
HYL_7
Ref
gsc0618
AAAL

waste_giant

dok

19小时前

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

using namespace std;

const int N = 510;
int g[N][N], dist[N], path[N];
bool st[N];
int n, m;

void print(int path[])
{
int i = n;
vector<int> tmp;
tmp.push_back(n);
while(path[i] != -1)
{
tmp.push_back(path[i]);
i = path[i];
}
int len = tmp.size();
for(int i = len - 1; i >= 0; i --)
if(i != 0)
{
printf("%d->",tmp[i]);
}
else cout << tmp[i];
}

int dijkstra()
{
memset(path, -1, sizeof path);
memset(dist, 0x3f, sizeof dist);

dist[1] = 0; //节点1到自身的距离为0
for(int i = 0; i < n; i++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
/*找到此时dist数组中距源点距离最小的点(也就是dist数组中没被标记过的点中最小值的下标)，
*/
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

for(int j = 1; j <= n; j ++)
{
//更新dist数组，从此时找到的点t开始扩展，比较从1到j的距离, 与从1到t加上从t到j的距离
// dist[j] = min(dist[j], dist[t] + g[t][j]);
if(dist[j] > dist[t] + g[t][j])
{
dist[j] = dist[t] + g[t][j];
path[j] = t;
}
}

st[t] = true; //访问过距离最短的点就标记
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

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

memset(g, 0x3f3f3f3f, sizeof g);

// for(int i = 0; i <= n; i ++)
// {
//     for(int j = 0; j <= m; j ++)
//         cout << g[i][j] << ' ';
//     cout << endl;
// }

while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
printf("最短路径之和：%d\n", dijkstra());
cout << "最短路径：";
print(path);

return 0;
}



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

using namespace std;

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

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);

dist[1] = 0; //节点1到自身的距离为0
for(int i = 0; i < n; i++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
/*找到此时dist数组中距源点距离最小的点(也就是dist数组中没被标记过的点中最小值的下标)，
*/
if(!st[j] && (t == - || dist[t] > dist[j]))
t = j;

for(int j = 1; j <= n; j ++)
{
//更新dist数组，从此时找到的点t开始扩展，比较从1到j的距离, 与从1到t加上从t到j的距离
dist[j] = min(dist[j], dist[t] + g[t][j]);
}

st[t] = true; //访问过距离最短的点就标记
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

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

memset(g, 0x3f3f3f3f, sizeof g);

// for(int i = 0; i <= n; i ++)
// {
//     for(int j = 0; j <= m; j ++)
//         cout << g[i][j] << ' ';
//     cout << endl;
// }

while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra();

return 0;
}



#include <iostream>

using namespace std;

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

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

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

}


#include <iostream>
#include <vector>

using namespace std;

const int N = 110;
int f[N][N];
int T, n, m;

int main()
{
cin >> T;
while(T --)
{
int w;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
cin >> w;
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w;
}
}
cout << f[n][m] << endl;

}

return 0;

}


#include <iostream>

using namespace std;

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

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 = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j]; //应该放在第二层循环这里
for(int k = 1; k <= s[i]; k ++)
if(k * v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
cout << f[n][m];
return 0;
}



#include <iostream>

using namespace std;

const int N = 1010;
int v[N], w[N];
int f[N], n, m;
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 = 1; j <= m; j ++)
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m];
return 0;

}


#include <iostream>

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];
int n, m;
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 = m; j >= 0; j --)
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

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


10天前
#include <iostream>

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];
int n, m;
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 = m; j >= 0; j --)
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

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


10天前
#include <iostream>

using namespace std;

int main()
{
int n;
cin >> n;
int cnt = 0;
if(n < 3) cout << n;
else{
if(n % 2 == 0)
{
cnt = n / 2 - 1;
cout << 3 * cnt + 2;
}
else
{
cnt = n/ 2;
cout << 3 * cnt + 1;
}

}
return 0;
}


10天前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 50;
int x[N], n;
int l, r;

int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int op;
cin >> op;
x[i] = op;
}
for(int i = 1; i < n; i ++)
if(abs(x[i]) > abs(x[0]) && x[i] < 0) r ++;
else if(abs(x[i]) < abs(x[0]) && x[i] > 0) l ++;

//如果第一个蚂蚁一个都没有感染的话，则总的就一个感染
if(x[0] > 0 && r == 0 || x[0] < 0 && l == 0) cout << 1;
else cout << l + r + 1;
return 0;

}