lxz

216

lxz
30天前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (p)
{
ListNode *n = p -> next;
p -> next = q;
q = p;
p = n;
}
return q;
}
};


lxz
1个月前
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010, M = N;
int n, m;
int dis[N], vis[N];
int h[N], e[M], ne[M], w[M], idx;

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

int spfa()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
queue<int> q;
q.push(1);
vis[1] = 1;
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = 0;
for (int i = h[t] ; i != -1 ; i = ne[i])
{
int j = e[i];
if (dis[j] > dis[t] + w[i])
{
dis[j] = dis[t] + w[i];
if (!vis[j]) q.push(j);
}
}
}
return dis[n] == 0x3f3f3f3f ? -1 : dis[n];
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
while (m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
int res = spfa();
if (res == -1) puts("impossible");
else cout << res;
return 0;
}


lxz
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

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

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

int main()
{
scanf("%d%d%d", &n, &m, &k);
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for (int i = 0 ; i < m ; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[i] = {a, b, c};
}
for (int i = 0 ; i < k ; i ++)
{
memcpy(backup, dis, sizeof(dis));
for (int j = 0 ; j < m ; j ++)
{
int a = edges[j].a, b = edges[j].b, c = edges[j].c;
dis[b] = min(dis[b], backup[a] + c);
}
}
if (dis[n] > 0x3f3f3f3f / 2) cout << "impossible";
else cout << dis[n];
return 0;
}


lxz
1个月前
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef pair<int, int> PII;

const int N = 150010, M = N;

int h[N], e[M], ne[M], W[M], idx;
int dis[N], vis[N];
int n, m;

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

int dijkstra()
{
dis[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while (heap.size())
{
auto tt = heap.top();
heap.pop();
if (vis[tt.second]) continue;
int dist = tt.first, ver = tt.second;
vis[ver] = 1;
for (int i = h[ver] ; i != -1 ; i = ne[i])
{
int j = e[i];
if (dis[j] > dist + W[i])
{
dis[j] = dist + W[i];
heap.push({dis[j], j});
}
}
}
if (dis[n] == 0x3f3f3f3f) return -1;
else return dis[n];
}

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

while (m --)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
}
cout << dijkstra();
return 0;
}


lxz
1个月前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int g[N][N], vis[N];
int dis[N];
int n, m;

void Dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for (int i = 0 ; i < n - 1 ; i ++)
{
int mini = -1;
for (int j = 1 ; j <= n ; j ++)
{
if (!vis[j] && (mini == -1 || dis[mini] > dis[j]))
mini = j;
}

for (int j = 1 ; j <= n ; j ++)
{
if (dis[j] > dis[mini] + g[mini][j]) dis[j] = dis[mini] + g[mini][j];
}
vis[mini] = 1;
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof(g));
for (int i = 0 ; i < m ; i ++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
g[a][b] = min(g[a][b], w);
}
Dijkstra();
if (dis[n] == 0x3f3f3f3f) cout << "-1";
else cout << dis[n];
return 0;
}


lxz
1个月前
#include <iostream>

using namespace std;

const int N = 100010;

int f[N], a[N];
int n;

int main()
{
scanf("%d", &n);
for (int i = 1 ; i <= n ; i ++)
scanf("%d", &a[i]);
f[1] = a[1];
int res = 1;
for (int i = 1 ; i <= n ; i ++)
{
int l = 1, r = res;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (f[mid] >= a[i]) r = mid - 1;
else l = mid;
}
if (f[l] < a[i])
{
f[l + 1] = a[i];
if (l == res) res ++;
}
else f[l] = a[i];
}
cout << res;
return 0;
}


lxz
1个月前
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int dp[N][N];

int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a, b);
for (int i = 1 ; i <= n ; i ++)
{
for (int j = 1 ; j <= m ; j ++)
{
if (a[i - 1] == b [j - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
else
dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
}
}
printf("%d", dp[n][m]);
return 0;
}


lxz
1个月前
#include <iostream>

using namespace std;

const int N = 1010;

int f[N], g[N], a[N];
int n;

int main()
{
scanf("%d", &n);
for (int i = 1 ; i <= n ; i ++) scanf("%d", &a[i]);
int ri, res = 0;
for (int i = 1 ; i <= n ; i ++)
{
f[i] = 1;
for (int j = 1 ; j < i ; j ++)
{
if (a[j] < a[i])
{
if (f[i] < f[j] + 1)
{
f[i] = f[j] + 1;
g[i] = j;
if (res < f[i])
{
res = f[i];
ri = i;
}
}
}
}
}
/*
for (int i = ri ; i != 0 ; i = g[i])
printf("%d ", a[i]);
puts("");
*/
printf("%d", res);

return 0;
}


lxz
1个月前
#include <iostream>

using namespace std;

const int N = 510, M = 0x3f3f3f3f;

int a[N][N];
int dp[N][N];
int n;

int main()
{
scanf("%d", &n);
int res = -M;
for (int i = 1 ; i <= n ; i ++)
for (int j = 1 ; j <= i ; j ++)
scanf("%d", &a[i][j]);
dp[1][1] = a[1][1];
for (int i = 2 ; i <= n ; i ++)
{
for (int j = 1 ; j <= i ; j ++)
{
if (j == i) dp[i][j] = dp[i - 1][j - 1] + a[i][j];
else if (j == 1) dp[i][j] = dp[i - 1][j] + a[i][j];
else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
}
}
for (int i = 1 ; i <= n ; i ++)
res = max(res, dp[n][i]);
cout << res;
return 0;
}


lxz
1个月前
#include <iostream>

using namespace std;

const int N = 110;

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

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1 ; i <= n ; i ++)
{
scanf("%d", &s[i]);
for (int j = 1 ; j <= s[i] ; j ++) scanf("%d%d", &v[i][j], &w[i][j]);
}
for (int i = 1 ; i <= n ; i ++)
{
for (int j = m ; j >= 0 ; j --)
{
for (int k = 1 ; k <= s[i] ; k ++)
{
if (j >= v[i][k]) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
}
}
}
printf("%d", dp[m]);
return 0;
}