## ABC375D - ABA
### 思路
求的是长度为 $3$ 的回文串
问题变成了，求对于每一个中间位置
左边和右边的一样的字符数量
显然，可以用前缀和类似的想法维护

...A.....AXA......A..

```cpp
int n;
long long ans, suml[300], sumr[300];
string s;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = (int)s.size();
    s = " " + s;
    for(int i = 1; i <= n; i++)
    {
        sumr[s[i]]++;
    }
    for(int i = 1; i <= n; i++)
    {
        suml[s[i - 1]]++;
        sumr[s[i]]--;
        for(int j = 'A'; j <= 'Z'; j++)
        {
            ans += suml[j] * sumr[j];
        }
    }
    cout << ans << '\n';
    return 0;
}
```
## P1807 - 最长路
```cpp
int dist[1510],vis[1510],n,m;
vector<P>G[1510];
queue<int>q;
void spfa()
{
    q.push(1);
    dist[1]=0; vis[1]=1;
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        vis[now]=0;
        for(int i=0;i<G[now].size();i++)
        {
            int x=G[now][i].first;
            if(dist[x]>dist[now]+G[now][i].second)
            {
                dist[x]=dist[now]+G[now][i].second;
                if(vis[x]==0) q.push(x),vis[x]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) dist[i]=1e9;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        G[x].push_back({y,-z});
    }
    spfa();
    if(dist[n]==1e9) cout<<-1<<endl;
    else cout<<-dist[n]<<endl;
    return 0;
}
```
## P1144 - 最短路计数
```cpp
const int maxn = 1e6 + 10;
struct edge
{
    int to, cost;
};
int n, m, s, dist[maxn], vis[maxn], ans[maxn];
vector<edge>G[maxn];
queue<int>q;
void spfa()
{
    for(int i = 1; i <= n; i++) dist[i] = 1e9;
    q.push(s); dist[s] = 0; vis[s] = 1; ans[s] = 1;
    while(q.empty() == 0)
    {
        int now = q.front(); q.pop(); vis[now] = 0;
        int siz = (int)G[now].size();
        for(int i = 0; i < siz; i++)
        {
            edge e = G[now][i];
            if(dist[e.to] > dist[now] + e.cost)
            {
                dist[e.to] = dist[now] + e.cost;
                ans[e.to] = ans[now];
                if(vis[e.to] == 0)
                {
                    q.push(e.to);
                    vis[e.to] = 1;
                }
            }
            else if(dist[e.to] == dist[now] + e.cost)
            {
                ans[e.to] = (ans[e.to] + ans[now]) % 100003;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    s = 1;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back({b, 1});
        G[b].push_back({a, 1});
    }
    spfa();
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}
```
## ABC375G 
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 2e5 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<__int128,int>P;
struct edge
{
    int x;
    __int128 cost;
};
vector<edge>G[maxn];
int n, m;
struct ee
{
    int x, y;
    __int128 z;
}e[maxn];
__int128 dis1[maxn], dis2[maxn], ans1[maxn], ans2[maxn];
priority_queue<P, vector<P>,greater<P>>q;
//以1号点为起点跑最短路
void dij1()
{
    for(int i = 1; i <= n; i++) dis1[i] = 1e18L;
    dis1[1] = 0; ans1[1] = 1; q.push({0, 1});
    while(q.empty() == 0)
    {
        P now = q.top(); q.pop();
        int v = now.second;//点的编号
        if(dis1[v] < now.first) continue;
        int siz = (int)G[v].size();
        for(int i = 0; i < siz; i++)
        {
            edge nxt = G[v][i];
            if(dis1[nxt.x] > dis1[v] + nxt.cost)
            {
                dis1[nxt.x] = dis1[v] + nxt.cost;
                ans1[nxt.x] = ans1[v];
                q.push({dis1[nxt.x], nxt.x});
            }
            else if(dis1[nxt.x] == dis1[v] + nxt.cost)
            {
                ans1[nxt.x] = (ans1[nxt.x] + ans1[v])
                    %(__int128)(1e15 + 7);
            }
        }
    }
}
//以2号点为起点跑最短路
void dij2()
{
    for(int i = 1; i <= n; i++) dis2[i] = 1e18L;
    dis2[n] = 0; ans2[n] = 1; q.push({0, n});
    while(q.empty() == 0)
    {
        P now = q.top(); q.pop();
        int v = now.second;//点的编号
        if(dis2[v] < now.first) continue;
        int siz = (int)G[v].size();
        for(int i = 0; i < siz; i++)
        {
            edge nxt = G[v][i];
            if(dis2[nxt.x] > dis2[v] + nxt.cost)
            {
                dis2[nxt.x] = dis2[v] + nxt.cost;
                ans2[nxt.x] = ans2[v];
                q.push({dis2[nxt.x], nxt.x});
            }
            else if(dis2[nxt.x] == dis2[v] + nxt.cost)
            {
                ans2[nxt.x] = (ans2[nxt.x] + ans2[v])
                    %(__int128)(1e15 + 7);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i].x = a; e[i].y = b; e[i].z = c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    dij1();
    dij2();
    for(int i = 1; i <= m; i++)
    {
        if(dis1[e[i].x] + e[i].z + dis2[e[i].y] == dis1[n]
           &&(ans1[e[i].x] * ans2[e[i].y])
           %(__int128)(1e15 + 7) == ans1[n])
        {
            cout << "Yes\n";
            continue;
        }
        if(dis1[e[i].y] + e[i].z + dis2[e[i].x] == dis1[n]
           &&(ans1[e[i].y] * ans2[e[i].x])
           %(__int128)(1e15 + 7) == ans1[n])
        {
            cout << "Yes\n";
            continue;
        }
        cout << "No\n";
    }
    return 0;
}
```