1. ```for(int i = 1 ; i <= n; i++) dis[i] = inf;```
2. dont use ```vis[]```
3.
```cpp
void dfs1(int v)
{
// cout<<v<<" ";
for (int i=0;i<g1[v].to.size();i++)
{
if (dis1[v]<dis1[g1[v].to[i]])
{
dis1[g1[v].to[i]]=min(a[g1[v].to[i]], dis1[v]);
dfs1(g1[v].to[i]);
}
//if (g1[v].vis[i]==0)
//{
// g1[v].vis[i]=1;
// dfs1(g1[v].to[i]);
//}
}
}
```
4. ```dfs2()``` 同理
by __My0217__ @ 2023-12-10 10:26:19
@[__My0217__](/user/784650)
1. 改为dis1[i]
by __My0217__ @ 2023-12-10 10:26:53
@[GODTREE](/user/776799) 忘at了
by __My0217__ @ 2023-12-10 10:27:43
我的100pts码:
```cpp
#include<cstdio>
#include<algorithm>
#include<vector>
#define inf 0x3fffffff
using namespace std;
vector<int> g[100005];
vector<int> _g[100005];
int w[100005];
int maxnode[100005], minnode[100005];
void find_min(int u)
{
for(int i = 0 ; i < g[u].size() ; i++)
{
if(minnode[g[u][i]] > minnode[u])
{
minnode[g[u][i]] = min(w[g[u][i]], minnode[u]);
find_min(g[u][i]);
}
}
return ;
}
void find_max(int u)
{
for(int i = 0 ; i < _g[u].size() ; i++)
{
if(maxnode[_g[u][i]] < maxnode[u])
{
maxnode[_g[u][i]] = max(w[_g[u][i]], maxnode[u]);
find_max(_g[u][i]);
}
}
return ;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d", &w[i]);
}
for(int i = 1 ; i <= m ; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if(z == 1)
{
g[x].push_back(y);
_g[y].push_back(x);
}
else
{
g[x].push_back(y);
g[y].push_back(x);
_g[x].push_back(y);
_g[y].push_back(x);
}
}
for(int i = 1 ; i <= n ; i++) minnode[i] = inf;
minnode[1] = w[1];
find_min(1);
maxnode[n] = w[n];
find_max(n);
//puts("");
//for(int i = 1 ; i <= n ; i++) printf("%d ", maxnode[i]);
int ans = 0;
for(int i = 1 ; i <= n ; i++)
{
ans = max(maxnode[i]-minnode[i], ans);
}
printf("%d", ans);
return 0;
}
```
by __My0217__ @ 2023-12-10 10:28:53
~~刚学OI做什么绿题~~
by cheng12 @ 2023-12-10 10:46:28