传送门 思路：dfs剪一下枝，竟然能过。 当前的大于最小值，88. DFS做法
if(sum>minnn) return ; /** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-02-15.18.22 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; vector<int>v[maxn]; int dp[maxn]; int G[201][201]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; int vis[201][201]; int n; int minnn=1e9; int sum=0; void dfs(int step) { if(sum>minnn) return ; if(step == n) { minnn = min(minnn, sum); return ; } for(int i = step + 1; i <= n; i++) { sum+=G[step][i]; dfs(i); sum-=G[step][i]; } } int main() { ios::sync_with_stdio(false); cin >> n; for(int i = 1; i <= n - 1; i++) for(int j = i + 1; j <= n; j++) cin >> G[i][j]; dfs(1); cout<<minnn<<endl; return 0; }DP两种做法 dp[j]表示到j站时的最少租金，m[i]ji]表示i到j站的租金。
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-02-16.13.35 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; int G[202][202]; int dp[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; int n ; int main() { ios::sync_with_stdio(false); memset(dp,INF,sizeof(dp)); dp[1]=0; cin >> n; for(int i = 1; i <= n - 1; i++) for(int j = i + 1; j <= n; j++) cin >> G[i][j]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dp[j]=min(dp[j],dp[i] + G[i][j]);//横向 纵向 cout<<dp[n]<<endl; return 0; }在这里 dp[i]表示到i站时的最少租金，G[j][i]表示j到i站的租金。
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-02-16.13.35 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; int G[202][202]; int dp[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; int n ; int main() { ios::sync_with_stdio(false); memset(dp,INF,sizeof(dp)); dp[1]=0; cin >> n; for(int i = 1; i <= n - 1; i++) for(int j = i + 1; j <= n; j++) cin >> G[i][j]; for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) dp[i]=min(dp[i],dp[j] + G[j][i]);//横向 纵向 cout<<dp[n]<<endl; return 0; }floyd多源最短路
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-03-09.33.52 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; const int N=201; //vector<int>v[maxn]; int dp[maxn]; int g[N][N]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q;///同dijk实现一样 可以解决负权问题 void floyd(int n){ for(int k=1;k<=n;k++) for(int i=1;i<= n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } int main() { ios::sync_with_stdio(false); memset(g,0x3f,sizeof(g)); int n; cin>>n; for(int i=1;i<=n;i++) g[i][i]=0;///初始化 int u=1,v=1,w; int t=n*(n-1)/2; while(t--){ cin>>w; if(v==n) { ++u; v=u; } g[u][++v]=w; } floyd(n); cout<<g[1][n]<<endl; return 0; }dijk
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-01-21.20.40 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; vector<int>vt[maxn]; int w[maxn], v[maxn]; int dp[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; struct edge { int v, w, next; ///这条边的下一边 edge() {} ///构造函数 edge(int _v, int _w, int _next) { ///构造函数 v = _v; w = _w; next = _next; } } e[maxn]; int head[maxn], size; void init() { memset(head, -1, sizeof(head)); size = 0; }// void insert(int u, int v, int w) { e[size] = edge(v, w, head[u]); ///u链接的第一条边 head[u] = size++; } void insert2(int u, int v, int w) {///插入一个无向边 insert(u, v, w); //insert(v, u, w); } int n, m; int dis[maxn]; bool vis[maxn]; void dijkstra(int u) { memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); dis[u] = 0; for(int i = 0; i < n; i++) { int mind = 1e9,minj=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]<mind){ minj=j; mind=dis[j]; } } if(minj==-1) return ; vis[minj]=1; for(int j=head[minj];~j;j=e[j].next){ int v=e[j].v; int w=e[j].w; if(!vis[v]&&dis[v]>dis[minj]+w) dis[v]=dis[minj]+w; } } } int main() { ios::sync_with_stdio(false); init(); int u=1, v=1, w; cin >>n; int t=n*(n-1)/2; while(t--) { cin >> w; if(v==n) { u++; v=u; } insert2(u, ++v, w); } dijkstra(1);///必须指定源点。 cout << dis[n]<<endl; return 0; }spfa
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-02-20.59.50 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; vector<int>v[maxn]; int dp[maxn]; vector<int>G[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q;///spfa///O(M+N)logN. struct edge {///邻接表的链表实现 int v, w, fail;/// 这条边练的顶点编号 边权 这条边的下一条边在数组中的编号。 edge() {} edge(int _v, int _w, int _fail) { v = _v; w = _w; fail = _fail; } } e[maxn]; int head[maxn], len;///每一个点连出的第一条边 void init() { ///初始化 memset(head, -1, sizeof(head)); len = 0;///当前图中的边数 } void add(int u, int v, int w) {///插入一条边/从连出的所有的边 e[len] = edge(v, w, head[u]);/// 这条边练的顶点编号 head[u]当前连出第一条边。 head[u] = len++;///修改为len++ }///图论模板多 void add2(int u, int v, int w) { add(u, v, w); //add(v, u, w); } int n, m; int dis[maxn]; bool vis[maxn]; void spfa(int u) { memset(vis, 0, sizeof(vis)); vis[u] = 1; ///判段结点是否在队列中 memset(dis, 0x3f, sizeof(dis)); ///只会截取第一个字节 dis[u] = 0; queue<int>q; q.push(u); while(!q.empty()) { u = q.front(); q.pop();///1.23 vis[u] = 0; for(int j = head[u]; ~j; j = e[j].fail) {///j=-1; int v = e[j].v; int w = e[j].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w;///松弛操作 if(!vis[v]) { q.push(v); vis[v] = 1; } } } } } int main() { ios::sync_with_stdio(false); init(); int u=1, v=1, w; cin >> n; int t=n*(n-1)/2; while(t--) { cin>> w; if(v==n) { u++; v=u; } add2(u,++v, w); } spfa(1); cout << dis[n] << endl; return 0; }