qp
by xuping @ 2023-10-25 12:24:59
看不懂，我用4个队列做的
by xuping @ 2023-10-25 12:25:52
同求，WA on #10
in
```cpp
12 40
1 1 1
1 3 0
2 6 1
2 1 0
2 4 1
2 3 0
3 8 0
3 6 1
3 3 1
4 4 0
4 1 0
4 3 1
4 8 1
5 3 1
5 4 1
5 2 0
5 9 0
5 6 1
6 5 1
6 9 0
7 9 0
7 5 1
7 1 1
7 3 1
8 8 0
8 12 0
9 7 0
9 10 1
9 3 0
9 12 1
10 6 0
10 7 1
10 12 1
10 11 1
11 5 1
11 8 0
11 10 0
12 8 1
12 10 1
12 12 0
```
out
```cpp
23
```
ans
```cpp
27
```
```cpp
#include<bits/stdc++.h>
#define cit const register unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("1.in","r",stdin),freopen("1.out","w",stdout)
using namespace std;constexpr unsigned N=101,M=1e5;
#define int register unsigned
#define ll long long
#define void inline void
struct A{unsigned v,w;inline bool operator<(const A&a)const{return w>a.w;}};bitset<M>c;
vector<A>a[M];unsigned char b[N][N];unsigned d[M],id[N][N][2],cnt;
#define pb emplace_back
void add(cit u,cit v,cit w){a[u].pb(A{v,w});a[v].pb(A{u,w});}
signed main(){open;int n,m;cin>>n>>m;memset(b,2,sizeof b);
while(m--){int x,y,z;cin>>x>>y>>z;b[x][y]=z;}
for(int i=1,j;i<=n;++i)for(j=1;j<=n;++j)id[i][j][0]=++cnt,id[i][j][1]=++cnt;
for(int i=1,j;i<=n;++i)for(j=1;j<=n;++j){cit t0=id[i][j][0],t1=id[i][j][1],
r0=id[i][j+1][0],r1=id[i][j+1][1],d0=id[i+1][j][0],d1=id[i+1][j][1];
if(b[i][j]==0){
if(b[i][j+1]==0)add(t0,r0,0);
else if(b[i][j+1]==1)add(t0,r1,1);
else if(b[i][j+1]==2)add(t0,r0,2),add(t0,r1,3);
if(b[i+1][j]==0)add(t0,d0,0);
else if(b[i+1][j]==1)add(t0,d1,1);
else if(b[i+1][j]==2)add(t0,d0,2),add(t0,d1,3);}
else if(b[i][j]==1){
if(b[i][j+1]==0)add(t1,r0,1);
else if(b[i][j+1]==1)add(t1,r1,0);
else if(b[i][j+1]==2)add(t1,r0,3),add(t1,r1,2);
if(b[i+1][j]==0)add(t1,d0,1);
else if(b[i+1][j]==1)add(t1,d1,0);
else if(b[i+1][j]==2)add(t1,d0,3),add(t1,d1,2);}
else if(b[i][j]==2){
if(b[i][j+1]==0)add(t0,r0,0),add(t1,r0,1);
else if(b[i][j+1]==1)add(t0,r1,1),add(t1,r1,0);
if(b[i+1][j]==0)add(t0,d0,0),add(t1,d1,1);
else if(b[i+1][j]==1)add(t0,d0,1),add(t1,d1,0);}}
priority_queue<A>q;memset(d,0xff,sizeof d);int s;
d[s=id[1][1][b[1][1]]]=0;int ans=~0;q.push(A{s,0});
while(q.size()){A t=q.top();q.pop();cit u=t.v;
for(A e:a[u]){cit v=e.v,w=e.w;if(!v)continue;
if(d[v]>d[u]+w){d[v]=d[u]+w;q.push(A{v,d[v]});}}}
if(b[n][n]^1)ans=min(ans,d[id[n][n][0]]);
if(b[n][n]^0)ans=min(ans,d[id[n][n][1]]);
cout<<(signed)ans;
}
```
by hgckythgcfhk @ 2024-02-27 16:29:43
为什么你可以把函数写在main里面
by hgckythgcfhk @ 2024-02-27 16:31:45