2015山東信息學夏令營 Day4T3 生產

【題目描述】

工廠為了生產一種復雜的產品，給各個生產部門制定了詳細的生產計劃。那么，就經常會有生產部門要把產品送到另一個生產部門作為原料。這是一個注重產品質量的工廠，所以每當有產品要從A部門運到B部門時，都要先從A部門送到質量檢驗處，檢驗合格后再從質量檢驗處運到B部門。

有些部門之間有傳送帶連接，廠長想知道每次將產品從一個部門運送到另一個部門最少需要多長時間。

【輸入格式】

第一行兩個整數n、m，n表示部門數量，m表示傳送帶數量。出于方便，1號部門是質量檢驗處。

接下來m行，每行三個整數u、v、w，表示有一條從u部門到v部門的傳送帶，傳送過去需要w個單位時間。注意傳送帶是單向的。

接下來一個整數q，表示有q次運送。

接下來q行，每行兩個數a、b，表示這一次要將產品從a部門運送到b部門。

【輸出格式】

????輸出q行，每行一個整數，表示這次運送最少需要的時間。若沒有傳送方案，輸出-1。

【樣例輸入】

5?5

1?2?3

1?3?5

4?1?7

5?4?1

5?3?1

3

4?2

5?3

2?3

【樣例輸出】

10

13

-1

【數據規模與約定】

30%的數據，n≤100，m≤500，w=1

60%的數據，n≤100，m≤5000

另20%的數據，q=1

100%的數據，2≤n≤3000，m≤100000，2≤a,b≤n，

q≤100000，1≤u,v≤n，1≤w≤10000

有些部門之間可能有多條傳送帶。

工廠的員工都非常盡職盡責，他們的認真和熱情決定了產品的完美，所以不必考慮產品不合格的情況。

?

思路：

1、最短路，A到1再到B的距離，等于1到B的距離加上1到A的距離

2、存者正反兩個圖，在反圖上求1到A距離，在正圖上求1到B的距離

代碼：

①官方標程（spfa + 鏈式前向星）

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 3050; const int M = 500050; const int inf = 987654321; int n,m,q; struct Edge {int u,v,w; }xu[M]; int point[N],to[M],next[M],val[M]; int dui[N],mina[N],minb[N],top,tail; bool indui[N]; void MakeMinLen(int x[]) {int i;dui[1]=1;top=0;tail=1;indui[1]=1;for(i=1;i<=n;i++)x[i]=inf;x[1]=0;while(top^tail){top++;if(top==N)top=0;int now=dui[top];int then=point[now];indui[now]=0;while(then){int tox=to[then];if(x[tox]>x[now]+val[then]){x[tox]=x[now]+val[then];if(!indui[tox]){indui[tox]=1;tail++;if(tail==N)tail=0;dui[tail]=tox;}}then=next[then];}} } void InitGraph() {int i;scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&xu[i].u,&xu[i].v,&xu[i].w);memset(point,0,sizeof point);for(i=1;i<=m;i++){next[i]=point[xu[i].v];point[xu[i].v]=i;to[i]=xu[i].u;val[i]=xu[i].w;}MakeMinLen(mina);memset(point,0,sizeof point);for(i=1;i<=m;i++){next[i]=point[xu[i].u];point[xu[i].u]=i;to[i]=xu[i].v;val[i]=xu[i].w;}MakeMinLen(minb); } void MakeAns() {scanf("%d",&q);while(q--){int a,b;scanf("%d%d",&a,&b);int res=mina[a]+minb[b];if(res>=inf)res=-1;printf("%d\n",res);} } int main() {freopen("data.in","r",stdin);freopen("data.out","w",stdout);InitGraph();MakeAns();return 0; }

②自己寫的，感覺dij快一點，一測發現比標程慢不少TAT

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define inf ~0U>>2 #define maxn 3005 using namespace std; struct orz{int d;int p;friend bool operator < (orz a,orz b){return a.d > b.d;} }; struct edge{int v;int w; }; priority_queue< orz > ss; vector<edge> g[maxn],op[maxn]; int n,m,q,flag = 0,v[maxn],d[maxn],opd[maxn]; void init(){cin>>n>>m;int u,v,w;edge tmp;for(int i = 1;i <= m;i++){scanf("%d%d%d",&u,&v,&w);tmp.v = v;tmp.w = w;g[u].push_back(tmp);tmp.v = u;op[v].push_back(tmp);}cin>>q;for(int i = 1;i <= n;i++) d[i] = opd[i] = inf; } void dij(){orz tmp;tmp.d = 0;tmp.p = 1;opd[1] = 0;ss.push(tmp);flag++;int x,dd,to,wei;edge j;while(!ss.empty()){tmp = ss.top();ss.pop();x = tmp.p;dd = tmp.d;if(v[x] == flag) continue;v[x] = flag;for(int i = 0;i < g[x].size();i++){j = g[x][i];to = j.v;wei = j.w;if(d[to] > dd + wei){d[to] = dd + wei;tmp.d = dd + wei;tmp.p = to;ss.push(tmp);}}} } void opdij(){orz tmp;tmp.d = 0;tmp.p = 1;opd[1] = 0;ss.push(tmp);flag++;int x,dd,to,wei;edge j;while(!ss.empty()){tmp = ss.top();ss.pop();x = tmp.p;dd = tmp.d;if(v[x] == flag) continue;v[x] = flag;for(int i = 0;i < op[x].size();i++){j = op[x][i];to = j.v;wei = j.w;if(opd[to] > dd + wei){opd[to] = dd + wei;tmp.d = dd + wei;tmp.p = to;ss.push(tmp);}}} } void ask(){int u,v;long long dn;for(int i = 1;i <= q;i++){scanf("%d%d",&u,&v);dn = opd[u] + d[v];if(dn >= inf) cout<<-1<<endl;else cout<<dn<<endl;} } int main(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);init();dij();opdij();ask();return 0; }

?

轉載于:https://www.cnblogs.com/hyfer/p/5811798.html

總結

以上是生活随笔為你收集整理的2015山东信息学夏令营 Day4T3 生产的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。