51nod3221祝寿(反向建图优化)

题目链接

感觉忘记了好多东西。 求有向图中其余点到一个点的最短距离可以将该图翻转后run dijkstra

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;ll gcd(ll a,ll b){if(a<0)a&＃61;-a;if(b<0)b&＃61;-b;return b&＃61;&＃61;0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag&＃61;false;char ch;while(!isdigit(ch&＃61;getchar()))(ch&＃61;&＃61;&＃39;-&＃39;)&&(flag&＃61;true);
for(res&＃61;ch-48;isdigit(ch&＃61;getchar());res&＃61;(res<<1)&＃43;(res<<3)&＃43;ch - 48);flag&&(res&＃61;-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans&＃61;1;if(b&＃61;&＃61;0){return ans%mod;}while(b){if(b%2&＃61;&＃61;1){b--;ans&＃61;ans*a%mod;}a&＃61;a*a%mod;b&＃61;b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans &＃61; 1;a%&＃61;p;while(b){if(b&1){ans &＃61; (ans*a)%p;--b;}a &＃61;(a*a)%p;b >>&＃61; 1;}return ans%p;}//逆元 (分子*qp(分母,mod-2,mod))%mod;const int manx&＃61;1e4&＃43;500;
const int mamx&＃61;2e5&＃43;5;ll head[3][manx],d[3][manx];
bool vis[3][manx];ll n,m,s,e,kk,ans;
ll k[3];struct node{ll v,next,w;
}a[3][mamx];
void add(ll u,ll v,ll w,ll pos)
{a[pos][&＃43;&＃43;k[pos]].next&＃61;head[pos][u];a[pos][k[pos]].w&＃61;w;a[pos][k[pos]].v&＃61;v;head[pos][u]&＃61;k[pos];
}
void dij(ll pos)
{memset(d[pos],inf,sizeof(d[pos]));// memset(vis[pos],0,sizeof(vis[pos]));d[pos][s]&＃61;0;priority_queue<pair<ll,ll> >q;q.push(mp(0,s));while(q.size()){ll u&＃61;q.top().se;q.pop();// if(vis[u]&&u&＃61;&＃61;s)return ;if(vis[pos][u]) continue;vis[pos][u]&＃61;1;for(int i&＃61;head[pos][u];i;i&＃61;a[pos][i].next){ll v&＃61;a[pos][i].v,w&＃61;a[pos][i].w;if(d[pos][v]>d[pos][u]&＃43;w){//printf("qwq %lld\n",d[v]); //松弛操作&＃xff0c;更新距离d[pos][v]&＃61;d[pos][u]&＃43;w;// printf("sad %lld %lld %lld %lld\n",d[u],u,res,d[v]);q.push(mp(-d[pos][v],v)); //把更新的距离和点入队&＃xff0c;这里距离取负变成小根堆}}}
}ll now[11111];
signed main(){read(n);read(m);ll pos;read(pos);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){ll x,y,z;read(x);read(y);read(z);add(x,y,z,2);add(y,x,z,1);}s&＃61;pos;dij(2);// k&＃61;0;dij(1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){//printf("Q%lld %lld\n",d[2][i],d[1][i]);if(d[2][i]&＃43;d[1][i]<inf){printf("%lld\n",d[2][i]&＃43;d[1][i]);continue;}printf("impossible\n");}}