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

using namespace std;

const int N = 600, INF = 0x3f3f3f3f;
int g[N][N], d[N];
bool vis[N];
int n;

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

    for(int i=0;i<n-1;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && (t==-1 || d[j]<d[t])) t=j;
        }

        for(int j=1;j<=n;j++){
            d[j]=min(d[j], d[t]+g[t][j]);
        }
        vis[t]=true;
    }

    return d[n];
}
int main()
{
    memset(g, 0x3f, sizeof g);
    int m;
    cin >> n >> m;
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a!=b) g[a][b]=min(g[a][b], c);
    }

    int ret = dijkstra();
    if(ret==INF) cout << -1;
    else cout << ret;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010;
int e[N], ne[N], h[N], idx;
int n, d[N];
int top[N], k;

void add(int a, int b){
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
bool topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!d[i]) q.push(i); 
    }

    while(q.size()){
        auto cur = q.front();
        top[k++] = cur;
        q.pop();
        for(int i=h[cur];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(!d[j]) q.push(j);
        }
    }

    return k==n;
}
int main()
{
    memset(h, -1, sizeof h);
    int m;
    cin >> n >> m;
    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b]++;
    }

    if(topsort()){
        for(int i=0;i<k;i++){
            printf("%d ", top[i]);
        }
    }
    else cout << -1;
    return 0;
}

法一：暴力算法 o^2

法二：双指针

法三：哈希表（插入x时，查target-x是否存在）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> heap;
        for(int i=0;i<nums.size();i++){
            if(heap.count(target-nums[i])){
                return {heap[target-nums[i]], i};
            }
            heap[nums[i]] = i;
            //注意在判定后再插入，预防nums[i]==target/2的情况
        }
        return {};
    }
};

错误的代码：

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int N = 30;

int n;
bool vis[N];
int g[N][N];

bool bfs(int a, int b){
    queue<int> q;
    q.push(a);
    vis[a]=true;
    while(q.size()){
        int cur = q.front();
        q.pop();
        for(int i=0;i<n;i++){
            if(vis[i] || !g[cur][i]) continue;
            vis[i]=true;
            q.push(i);
            if(i==b) return true;
        }
    }
    return false;
}
int main()
{
    int m;
    cin >> n >> m;

    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b]=g[b][a]=1;
    }

    int a, b;
    cin >> a >> b;
    if(bfs(a,b)) printf("There is a path between %d and %d.", a, b);
    else printf("There is no path between %d and %d.", a, b);
    return 0;
}

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

using namespace std;

const int N = 100010;
int m, n;
int h[N], ne[N], e[N], idx;
int d[N], q[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int bfs(){
    memset(d, -1, sizeof d);
    d[1]=0;

    int hh=0, tt=0;
    q[0]=1;
    while(hh<=tt){
        int t = q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q[++tt]=j;
            }
        }
    }
    return d[n];
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs();
    return 0;
}

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

using namespace std;

const int N = 100010, M = 2*N;
int n;
int h[N], e[M], ne[M], idx;
bool vis[N];
int ans = N;
void add(int a, int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u){//返回以u为根的子树中点的数量
    vis[u]=true;

    int sum=1, res=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!vis[j]){
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n-sum);
    ans = min(ans, res);

    return sum;
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i=0;i<n-1;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);add(b, a);
    }

    dfs(1);
    cout << ans;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

char g[20];
int bfs(string start){
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> d;
    int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};

    q.push(start);
    d[start] = 0;
    while(q.size()){
        string cur = q.front();
        q.pop();
        if(cur==end) return d[cur];

        int dis = d[cur]+1;
        int k=cur.find('x');
        int x=k/3, y=k%3;
        for(int i=0;i<4;i++){
            int neX=x+dx[i], neY=y+dy[i];
            if(neX>=0 && neX<3 && neY>=0 && neY<3){
                swap(cur[neX*3+neY], cur[k]);
                if(d.count(cur)==0){
                    d[cur]=dis;
                    q.push(cur);
                }
                swap(cur[neX*3+neY], cur[k]);
            }
        }
    }
    // return d[end];
    return -1;
}
int main()
{
    string state;
    char c;
    for(int i=0;i<9;i++){
        cin >> c;
        state += c;
    }

    // if(state=="12345678x") cout << 0;
    // else{
    //     int res=bfs(state);
    //     if(res) cout << res;
    //     else cout << -1;
    // }
    cout << bfs(state);

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;
int path[N];
bool vis1[N], vis2[N], col[N];
int n;
char g[N][N];

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) puts(g[i]);
        puts("");
        return;
    }

    for(int i=0;i<n;i++){
        if(!col[i] && !vis1[u+i] && !vis2[n-u+i]){
            g[u][i]='Q';
            col[i]=vis1[u+i]=vis2[n-u+i]=true;
            dfs(u+1);
            col[i]=vis1[u+i]=vis2[n-u+i]=false;
            g[u][i]='.';
        }
    }
}
int main()
{
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
bool vis[N];

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) printf("%d ", path[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            path[u]=i;
            vis[i]=true;
            dfs(u+1);
            vis[i]=false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

#include <iostream>
#include <cstdio>

using namespace std;

//unsigned long long 溢出代替取模2^64
typedef unsigned long long ULL;

const int N = 100010, b=131;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int n,m;
    scanf("%d%d%s", &n, &m, str+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*b;
        h[i]=h[i-1]*b+str[i];
    }

    while(m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1)==get(l2, r2)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}