类似于最短路的网络流，而且还要保证每个点经过一次，拆点就比较方便了。

连边怎么连？要保证最大流是n（每个点经过一次）还要能从直接跳转

将每个点拆点。

源点向每个点的入点连一条容量为1费用为0的边。

源点向每个点的出点连一条容量为1费用为瞬移到该点所需时间的边。

每个点的出点向汇点连一条容量为1费用为0的边。

对于每条边(i,j)，从i点入点向j点出点连一条容量为1费用为航路所需时间的边。

就是，到了每个点，出点会标记到了这个点（连向T一条边的流量会流过去）

走从S到一个点x的入点边，相当于选择从这个点x走要一条边到达另一个点

走。。。。。。。出点边，相当于直接瞬移。

费用都是正的，所以每个点一定被经过恰好一次。

把这些流按一定顺序排序，走出来的一定就是一个合法的路径。

流到该点出点的某入点对应的星球，在之前的某一时刻一定由某种合法方式达到过，追溯到头一定是某个瞬移到的点（因为图中没有环），“追溯”的过程就是这一条路径。

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1608;const int M=15000+5;const int inf=0x3f3f3f3f;int n,m,s,t;struct node{    int nxt,to;    int w,v;}e[2*(N+M+N)];int hd[N],cnt=1;void add(int x,int y,int w,int v){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].w=w;    e[cnt].v=v;    hd[x]=cnt;        e[++cnt].nxt=hd[y];    e[cnt].to=x;    e[cnt].w=0;    e[cnt].v=-v;    hd[y]=cnt;}int incf[N],dis[N];int pre[N];bool vis[N];queue
      
       q;bool spfa(){    while(!q.empty()) q.pop();    memset(vis,0,sizeof vis);    memset(dis,inf,sizeof dis);    dis[s]=0;    incf[s]=inf;    pre[s]=0;    q.push(s);    while(!q.empty()){        int x=q.front();q.pop();        vis[x]=0;        for(reg i=hd[x];i;i=e[i].nxt){            int y=e[i].to;            if(e[i].w&&dis[y]>dis[x]+e[i].v){                dis[y]=dis[x]+e[i].v;                pre[y]=i;                incf[y]=min(e[i].w,incf[x]);                if(!vis[y]){                    vis[y]=1;                    q.push(y);                }            }            }    }    if(dis[t]==inf) return false;    return true;}int ans,maxflow;void upda(){    int x=t;    while(pre[x]){        e[pre[x]].w-=incf[t];        e[pre[x]^1].w+=incf[t];        x=e[pre[x]^1].to;    }    ans+=incf[t]*dis[t];    maxflow+=incf[t];    //cout<<" ans "<
       
        <<" "<
        
         <
         
          y) swap(x,y);        add(x,y+n,1,z);    }    while(spfa()) upda();    //cout<<" liu "<
          
           <