• 欢迎光临~

# Link With Running || 杭电多校第四场T2 || Dijkstra + Tarjan + SPFA

ei 和 pi 大于等于 0。保证答案存在且可输出。

```  1 #include<bits/stdc++.h>
2 #define ll long long
3 #define min(a,b) ((a)<(b)?(a):(b))
4 using namespace std;
5 const int maxn=1e5+10,maxm=3e5+10;
6 const ll inf=(ll)1e18+7;
8 ll dis[maxn];
9 int dfn[maxn],low[maxn],col[maxn],num_col,st[maxn],ix,tp,din[maxn];
10 queue<int>que;
11 bool vis[maxn];
12 struct Node{
13     int id,eg;
14     ll dis;
15     bool operator <(const Node&a)const{
16         return (a.dis<dis);
17     }
18 }nd;
19 priority_queue<Node>q;
20 struct Edge{
21     int from,to,nx;
22     ll e,p;
23 }edge[maxm],eg[maxm];
24 void Add_edge(int from,int to,ll e,ll p){
26     edge[num_edge].from=from;
27     edge[num_edge].to=to;
28     edge[num_edge].e=e;
29     edge[num_edge].p=p;
31     return;
32 }
33 void Add_eg(int i){
34     int from=edge[i].from,to=edge[i].to,p=edge[i].p;
36     eg[num_eg].from=from;
37     eg[num_eg].to=to;
38     eg[num_eg].p=p;
40     return;
41 }
42 void Dij(){
43     while(!q.empty()) q.pop();
44     nd.id=1;nd.dis=0;
45     q.push(nd);
46     dis[1]=0;
47     for(int i=2;i<=n;i++) dis[i]=inf;
48     while(!q.empty()){
49         nd=q.top();
50         q.pop();
51         int u=nd.id;
52         if(vis[u]){
53             if(u==n) break;
54             continue;
55         }
56         vis[u]=1;
58             int v=edge[i].to;
59             if(dis[u]+edge[i].e<dis[v]){
60                 dis[v]=dis[u]+edge[i].e;
61                 nd.id=v; nd.dis=dis[v];
62                 nd.eg=i;
63                 q.push(nd);
64             }
65         }
66     }
67
68     for(int u=1;u<=n;u++){
69         if(dis[u]==inf) continue;
71             int v=edge[i].to;
73         }
74     }
75     return;
76 }
77 void Tarjan(int x){
78     st[++tp]=x;
79     vis[x]=1;
80     dfn[x]=low[x]=++ix;
82         int y=eg[i].to;
83         if(dfn[y]==0){
84             Tarjan(y);
85             low[x]=min(low[x],low[y]);
86         }
87         else if(vis[y]) low[x]=min(low[x],dfn[y]);
88     }
89     if(dfn[x]==low[x]){
90         num_col++;
91         do{
92             vis[st[tp]]=0;
93             col[st[tp]]=num_col;
94             tp--;
95         }while(st[tp+1]!=x);
96     }
97     return;
98 }
99 void Work(){
100     num_edge=0;
102     for(int i=1;i<=num_eg;i++){
103         int u=eg[i].from,v=eg[i].to;
104         if(col[u]!=col[v])
106     }
107     return;
108 }
109 void SPFA(){
110     que.push(col[1]);
111     dis[col[1]]=0;
112     while(!que.empty()){
113         int x=que.front();
114         que.pop();
116             int y=edge[i].to;
117             if(dis[y]<dis[x]+edge[i].p)
118                 dis[y]=dis[x]+edge[i].p;
119             if(--din[y]==0) que.push(y);//DAG优化。
120         }
121     }
122     return;
123 }
124 int main(){
125     scanf("%d",&T);
126     while(T--){
127         num_edge=0;num_eg=0;
130         //init
131
132         scanf("%d%d",&n,&m);
133         int a,b; ll c,d;
134         for(int i=1;i<=m;i++){
135             scanf("%d%d%lld%lld",&a,&b,&c,&d);
137         }
138         //从1到n最短路dij
139         Dij();
140         printf("%lld ",dis[n]);
141         //init
142         num_col=0;
143         tp=ix=0;
144         memset(vis,0,sizeof(vis));
145         memset(dfn,0,sizeof(dfn));
146         memset(low,0,sizeof(low));
147         memset(st,0,sizeof(st));
148         //init
149         Tarjan(1);
150         //init
151         memset(din,0,sizeof(din));
152         memset(dis,0,sizeof(dis));
153         //init;
154         Work();
155         SPFA();
156         printf("%lldn",dis[col[n]]);
157     }
158     return 0;
159 }```
View Code

By: AlenaNuna